A simple algorithm for constructing Szemerédi's regularity partition (Q1283876)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1271227
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A simple algorithm for constructing Szemerédi's regularity partition |
scientific article; zbMATH DE number 1271227 |
Statements
A simple algorithm for constructing Szemerédi's regularity partition (English)
0 references
31 March 1999
0 references
Szemerédi's regularity lemma is often used to prove the existence of certain objects and if in addition one whises to construct them, one needs a constructive version of the lemma. This was provided by \textit{N. Alon}, \textit{R. A. Duke}, \textit{H. Lefmann}, \textit{V. Rödl} and \textit{R. Yuster} [J. Algorithms 16, No. 1, 80-109 (1994; Zbl 0794.05119)]. In this short paper, the authors give another construction based on the use of singular values of matrices.
0 references
regularity lemma
0 references
0.8294662237167358
0 references
0.8291637897491455
0 references
