×

The algorithmic aspects of the regularity lemma. (English) Zbl 0794.05119

The regularity lemma of Szemeredi asserts that every graph can be partitioned in a certain regular way. This result has numerious applications, but its known proof is not algorithmic. It is shown how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68R05 Combinatorics in computer science
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI Link