The Algorithmic Aspects of the Regularity Lemma

1994/01/01 by Noga Alon, N. Alon, Richard A. Duke +7 · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constructive #Discrete mathematics #Embedding #Graph #Graph partition #Graph property #Lemma (botany) #Limits and Structures in Graph Theory #Line graph #Mathematics #Partition (number theory) #Vertex (graph theory) #Voltage graph

paper · doi:10.1006/jagm.1994.1005

crossref issued 1994/01/01 · crossref published 1994/01/01 · crossref published-print 1994/01/01 · openalex publication_date 1994/01/01 · crossref created 2002/10/06 · crossref deposited 2019/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28 · crossref indexed 2026/08/03

Citations

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem

Cited by

• Regularity Lemmas and Combinatorial Algorithms
• Regular partitions of gentle graphs
• Hardness of fully dense problems
• Grothendieck‐Type Inequalities in Combinatorial Optimization
• Approximating the Cut-Norm via Grothendieck's Inequality
• Szemerédi regularity lemma [wikipedia]