A simple algorithm for constructing Szemerédi's regularity partition (Q1283876): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Latest revision as of 02:47, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A simple algorithm for constructing Szemerédi's regularity partition |
scientific article |
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
