An Optimal Algorithm for Checking Regularity

DOI10.1137/S0097539702408223MaRDI QIDQ4429683zbMATH OpenOpenAlexFDO

Authors Yoshiharu Kohayakawa, Vojtěch Rödl, Luboš Thoma

Publication date 28 September 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539702408223

zbMATH Keywords

expanderregular pairsquasi-randomnessdeterministic samplingSzemerédi's regularity lemma

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2119673
• An optimal algorithm for finding Frieze-Kannan regular partitions
• scientific article; zbMATH DE number 1256685
• Perfect matchings via uniform sampling in regular bipartite graphs
• A fast new algorithm for weak graph regularity

Cited in

(18)

• Constructive packings by linear hypergraphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• An optimal algorithm for finding Frieze-Kannan regular partitions
• scientific article; zbMATH DE number 4016574 (Why is no real title available?)
• scientific article; zbMATH DE number 2119673 (Why is no real title available?)
• Grothendieck-type inequalities in combinatorial optimization
• Additive approximation for edge-deletion problems
• Some Cubic Time Regularity Algorithms for Triple Systems
• Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs
• Constructive Packings of Triple Systems
• A fast new algorithm for weak graph regularity
• On regularity lemmas and their algorithmic applications
• OPTi's Algorithm for Discreteness Determination
• Embedding graphs with bounded degree in sparse pseudorandom graphs
• An optimal choice problem for a set of checking procedures
• scientific article; zbMATH DE number 1512671 (Why is no real title available?)

This page was built for publication: An Optimal Algorithm for Checking Regularity

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