TY - GEN

T1 - The algorithmic aspects of the regularity lemma

AU - Alon, N.

AU - Duke, R. A.

AU - Lefmann, H.

AU - Rödl, V.

AU - Yuster, R.

PY - 1992/1/1

Y1 - 1992/1/1

N2 - The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC1.

AB - The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC1.

UR - http://www.scopus.com/inward/record.url?scp=85032933992&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032933992&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1992.267804

DO - 10.1109/SFCS.1992.267804

M3 - Conference contribution

AN - SCOPUS:85032933992

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 473

EP - 481

BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

PB - IEEE Computer Society

T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

Y2 - 24 October 1992 through 27 October 1992

ER -