A simple algorithm for constructing Szemerédi's regularity partition

MaRDI QIDQ1283876zbMATH OpenFDO

Authors Alan Frieze, R. Kannan

Publication date 31 March 1999

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119828, http://www.emis.de/journals/EJC/Volume_6/v6i1toc.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

regularity lemma

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• scientific article; zbMATH DE number 1512671
• The Algorithmic Aspects of the Regularity Lemma
• An algorithmic hypergraph regularity lemma
• scientific article; zbMATH DE number 1256685

Cited in

(9)

• Regularity lemmas for clustering graphs
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Combinatorial and computational aspects of graph packing and graph decomposition
• On regularity lemmas and their algorithmic applications
• The sparse regularity method with Schatten norms and entropy
• Spectral algorithms in higher-order Fourier analysis

This page was built for publication: A simple algorithm for constructing Szemerédi's regularity partition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1283876)