An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions

DOI10.1017/S0963548314000200zbMath1371.05141OpenAlexW2141649469MaRDI QIDQ5364234

Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtěch Rödl, Aasaf Shapira, Domingos jun. Dellamonica

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548314000200

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)

Related Items (8)

Approximating the Rectilinear Crossing Number ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Amplification and Derandomization without Slowdown ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Graph summarization with quality guarantees ⋮ Erratum: On Regularity Lemmas and their Algorithmic Applications ⋮ A fast new algorithm for weak graph regularity ⋮ Approximating the rectilinear crossing number

Cites Work

• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Quick approximation to matrices and applications
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Bounds for graph regularity and removal lemmas
• A Deterministic Algorithm for the Frieze–Kannan Regularity Lemma
• On sets of integers containing k elements in arithmetic progression
• The Algorithmic Aspects of the Regularity Lemma
• An Optimal Algorithm for Checking Regularity
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph

This page was built for publication: An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions