An Optimal Algorithm for Checking Regularity
From MaRDI portal
Publication:4429683
DOI10.1137/S0097539702408223zbMath1025.05056OpenAlexW2052318581MaRDI QIDQ4429683
Lubos Thoma, Yoshiharu Kohayakawa, Vojtěch Rödl
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
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (13)
Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Embedding graphs with bounded degree in sparse pseudorandom graphs ⋮ Additive approximation for edge-deletion problems ⋮ Constructive Packings of Triple Systems ⋮ A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing ⋮ Some Cubic Time Regularity Algorithms for Triple Systems ⋮ An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Constructive Packings by Linear Hypergraphs ⋮ A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma ⋮ A fast new algorithm for weak graph regularity ⋮ Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs
This page was built for publication: An Optimal Algorithm for Checking Regularity
