An Optimal Algorithm for Finding Frieze–Kannan Regular Partitions
From MaRDI portal
Publication:5364234
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
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
