A simple algorithm for constructing Szemerédi's regularity partition
type: Item
instance of: scholarly article
title: A simple algorithm for constructing Szemerédi's regularity partition
zbMATH Open document ID: 0917.05070
published in: The Electronic Journal of Combinatorics
publication date: 1999-03-31T00:00:00Z
full work available at URL: https://eudml.org/doc/119828
full work available at URL: v6i1toc.html
review text: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1271227
zbMATH Keywords: regularity lemma
author: Alan Frieze
author: R. Kannan
reviewed by: G. Gutin
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1271227