The Algorithmic Aspects of the Regularity Lemma
From MaRDI portal
Publication:4289842
DOI10.1006/jagm.1994.1005zbMath0794.05119OpenAlexW2083580384WikidataQ105583227 ScholiaQ105583227MaRDI QIDQ4289842
Noga Alon, Raphael Yuster, Hanno Lefmann, Richard A. Duke, Vojtěch Rödl
Publication date: 5 June 1994
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/775729f00a7c6218104e3dd6dcb0f8d8e2114d63
Combinatorics in computer science (68R05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)
Related Items
NOTES ON THE STABLE REGULARITY LEMMA, Grothendieck-Type Inequalities in Combinatorial Optimization, Embedding graphs with bounded degree in sparse pseudorandom graphs, Testing Odd-Cycle-Freeness in Boolean Functions, On characterizing hypergraph regularity, The Bipartite QUBO, A Folkman Linear Family, Induced arithmetic removal: complexity 1 patterns over finite fields, Separating Hash Families: A Johnson-type bound and New Constructions, Minimum \(H\)-decompositions of graphs, Additive approximation for edge-deletion problems, Random graphs with monochromatic triangles in every edge coloring, New applications of the polynomial method: The cap set conjecture and beyond, Integer and fractional packings of hypergraphs, Packing directed cycles efficiently, On the Interplay Between Strong Regularity and Graph Densification, On the local structure of oriented graphs -- a case study in flag algebras, Efficient Removal Lemmas for Matrices, The edit distance function of some graphs, Efficient removal lemmas for matrices, Testing Linear-Invariant Properties, Bounds for graph regularity and removal lemmas, Constructive Packings of Triple Systems, Making an H $H$‐free graph k $k$‐colorable, Minimum degree and the graph removal lemma, Rainbow connections of graphs: a survey, A further extension of Rödl's theorem, Spectral extremal graphs for disjoint cliques, Some Cubic Time Regularity Algorithms for Triple Systems, Local-vs-global combinatorics, An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions, Easily Testable Graph Properties, On Regularity Lemmas and their Algorithmic Applications, Hamilton decompositions of regular expanders: applications, The maximum spectral radius of graphs without friendship subgraphs, Amplification and Derandomization without Slowdown, Combinatorial and computational aspects of graph packing and graph decomposition, Extremal results in sparse pseudorandom graphs, Regular partitions of gentle graphs, An approximate version of Sumner's universal tournament conjecture, Hamilton cycles in dense vertex-transitive graphs, Threshold behavior of multi-path random key pre-distribution for sparse wireless sensor networks, On the KŁR conjecture in random graphs, Spanning 3-colourable subgraphs of small bandwidth in dense graphs, A blow-up lemma for approximate decompositions, Hardness and algorithms for rainbow connection, Constructive Packings by Linear Hypergraphs, Graph summarization with quality guarantees, Regularity lemmas for stable graphs, Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs, Maximum dispersion problem in dense graphs, Almost given length cycles in digraphs, Regularity lemmas for clustering graphs, The effect of induced subgraphs on quasi-randomness, Regular pairs in sparse random graphs I, Finding bipartite subgraphs efficiently, Partitioning problems in dense hypergraphs, On random sampling in uniform hypergraphs, Testing subgraphs in directed graphs, Path and cycle decompositions of dense graphs, A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma, A fast new algorithm for weak graph regularity, The Induced Removal Lemma in Sparse Graphs, A fast parallel algorithm for finding Hamiltonian cycles in dense graphs, Estimating parameters associated with monotone properties, Cycle factors in dense graphs, Highly connected coloured subgraphs via the regularity Lemma, Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs, Weak quasi-randomness for uniform hypergraphs, Large planar subgraphs in dense graphs, Proof of a conjecture of Bollobás and Kohayakawa on the Erdős-Stone theorem, Unnamed Item, Every Monotone 3-Graph Property is Testable, Hypergraphs, quasi-randomness, and conditions for regularity, The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition, The Approximate Loebl--Komlós--Sós Conjecture IV: Embedding Techniques and the Proof of the Main Result
