|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Revealing Structure in Large Graphs: Szemer'edi's Regularity Lemma and its Use in Pattern Recognition | | Marcello Pelillo
; Ismail Elezi
; Marco Fiorucci
; | | Date: |
21 Sep 2016 | | Abstract: | Introduced in the mid-1970’s as an intermediate step in proving a
long-standing conjecture on arithmetic progressions, Szemer’edi’s regularity
lemma has emerged over time as a fundamental tool in different branches of
graph theory, combinatorics and theoretical computer science. Roughly, it
states that every graph can be approximated by the union of a small number of
random-like bipartite graphs called regular pairs. In other words, the result
provides us a way to obtain a good description of a large graph using a small
amount of data, and can be regarded as a manifestation of the all-pervading
dichotomy between structure and randomness. In this paper we will provide an
overview of the regularity lemma and its algorithmic aspects, and will discuss
its relevance in the context of pattern recognition research. | | Source: | arXiv, 1609.6583 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER