Regularity Lemmas and Combinatorial Algorithms

DOI10.1109/FOCS.2009.76zbMath1292.05242MaRDI QIDQ5171230

Nikhil Bansal, R. Ryan Williams

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Data structures (68P05) Randomized algorithms (68W20)

Related Items (16)

A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ An improved combinatorial algorithm for Boolean matrix multiplication ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Pushdown reachability with constant treewidth ⋮ Bounds for graph regularity and removal lemmas ⋮ Unnamed Item ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Linear-space data structures for range mode query in arrays ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication

This page was built for publication: Regularity Lemmas and Combinatorial Algorithms