An Optimal Algorithm for Checking Regularity

Yoshiharu Kohayakawa, V. Rödl, Luboš Thoma

Type: Article

Publication Date: 2003-01-01

Citations: 51

DOI: https://doi.org/10.1137/s0097539702408223

View Publication

Locations

SIAM Journal on Computing - View

Similar Works

Action	Title	Year	Authors
+	An optimal algorithm for checking regularity: (extended abstract)	2002	Yoshiharu Kohayakawa V. Rödl Luboš Thoma
+	Algorithmic Aspects of Regularity	2000	Yoshiharu Kohayakawa V. Rödl
+ PDF Chat	The algorithmic aspects of the regularity lemma	1992	Noga Alon
+ PDF Chat	Revealing structure in large graphs: Szemerédi’s regularity lemma and its use in pattern recognition	2016	Marcello Pelillo Ismail Elezi Marco Fiorucci
+	Revealing Structure in Large Graphs: Szemer\'edi's Regularity Lemma and its Use in Pattern Recognition	2016	Marcello Pelillo Ismail Elezi Marco Fiorucci
+	Revealing Structure in Large Graphs: Szemerédi's Regularity Lemma and its Use in Pattern Recognition	2016	Marcello Pelillo Ismail Elezi Marco Fiorucci
+	Extremal Hypergraph Theory and Algorithmic Regularity Lemma for Sparse Graphs	2010	Rerum Naturalium Mathematisch-Naturwissenschaftlichen Fakultät
+ PDF Chat	On Regularity Lemmas and their Algorithmic Applications	2017	Jacob Fox László Lovász Yufei Zhao
+	On regularity lemmas and their applications	2016	Jacob Fox László Lovász Yufei Zhao
+	An Algorithmic Hypergraph Regularity Lemma	2015	Brendan Nagle Vojtěch Rödl Mathias Schacht
+	An algorithmic hypergraph regularity lemma	2016	Brendan Nagle Vojtěch Rödl Mathias Schacht
+	A sparse regular approximation lemma	2017	Guy Moshkovitz A. Shapira
+ PDF Chat	Approximate Hypergraph Partitioning and Applications	2010	Eldar Fischer Arie Matsliah A. Shapira
+	A Sparse Regular Approximation Lemma	2016	Guy Moshkovitz A. Shapira
+	Szémeredi's regularity lemma and its applications in combinatorics	2006	Jonas Hägglund
+ PDF Chat	Can a Graph Have Distinct Regular Partitions?	2009	Noga Alon A. Shapira Uri Stav
+ PDF Chat	Can a Graph Have Distinct Regular Partitions?	2007	Noga Alon A. Shapira Uri Stav
+	A Sparse Regular Approximation Lemma	2016	Guy Moshkovitz A. Shapira
+	A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs	2020	Viresh Patel Fabian Stroh
+ PDF Chat	A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs	2022	Viresh Patel Fabian Stroh

Works That Cite This (43)

Action	Title	Year	Authors
+	On Algorithmic Fractional Packings of Hypergraphs	2012	Jill S. Dizona
+ PDF Chat	A Characterization for Sparse $\varepsilon$-Regular Pairs	2007	Stefanie Gerke Angelika Steger
+ PDF Chat	A fast new algorithm for weak graph regularity	2019	Jacob Fox László Lovász Yufei Zhao
+ PDF Chat	A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma	2011	Domingos Dellamonica Subrahmanyam Kalyanasundaram Daniel M. Martin Vojtěch Rödl A. Shapira
+	An algorithmic hypergraph regularity lemma	2016	Brendan Nagle Vojtěch Rödl Mathias Schacht
+	Extremal Hypergraph Theory and Algorithmic Regularity Lemma for Sparse Graphs	2010	Rerum Naturalium Mathematisch-Naturwissenschaftlichen Fakultät
+	Hypergraphs, Quasi-randomness, and Conditions for Regularity	2002	Yoshiharu Kohayakawa Vojtěch Rödl Jozef Skokan
+	An algorithmic hypergraph regularity lemma	2017	Brendan Nagle Vojtěch Rödl Mathias Schacht
+ PDF Chat	Revealing structure in large graphs: Szemerédi’s regularity lemma and its use in pattern recognition	2016	Marcello Pelillo Ismail Elezi Marco Fiorucci
+	Constructive Packings of Triple Systems	2017	Brendan Nagle

Works Cited by This (17)

Action	Title	Year	Authors
+	Szemeredi''s Regularity Lemma and its applications in graph theory	1995	János Komlós Miklós Simonovits
+	Probabilistic Methods in Combinatorics	1974	Joel Spencer
+	Constructive Quasi-Ramsey Numbers and Tournament Ranking	1999	Andrzej Czygrinow S. Poljak V. Rödl
+	Matrix multiplication via arithmetic progressions	1990	Don Coppersmith S. Winograd
+	Explicit expanders and the Ramanujan conjectures	1986	Alexander Lubotzky Ralph S. Phillips Peter Sarnak
+	A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph	1995	Richard A. Duke Hanno Lefmann V. Rödl
+	On graphs with small subgraphs of large chromatic number	1985	V. Rödl Richard A. Duke
+ PDF Chat	Pairwise Independence and Derandomization	2005	Michael Luby Avi Wigderson
+ PDF Chat	Quasi-random set systems	1991	Fan Chung Ronald Graham
+	Quasi‐random tournaments	1991	Fan Chung Ronald Graham