A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
DOI10.1007/978-3-642-22935-0_42zbMath1343.68107OpenAlexW2293834400MaRDI QIDQ3088120
Daniel M. Martin, Vojtěch Rödl, Asaf Shapira, Subrahmanyam Kalyanasundaram, Domingos jun. Dellamonica
Publication date: 17 August 2011
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_42
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- Eigenvalues and expanders
- Quick approximation to matrices and applications
- A simple algorithm for constructing Szemerédi's regularity partition
- Lower bounds of tower type for Szemerédi's uniformity lemma
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Approximating the cut-norm via Grothendieck's inequality
- Very large graphs
- Rapid Multiplication of Rectangular Matrices
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- On sets of integers containing k elements in arithmetic progression
- The Algorithmic Aspects of the Regularity Lemma
- An Optimal Algorithm for Checking Regularity
- Lecture notes on the DiPerna–Lions theory in abstract measure spaces
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- Regularity Lemmas and Combinatorial Algorithms
This page was built for publication: A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma
