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

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68P05: Data structures

68W20: Randomized algorithms

Related Items

Fast matrix multiplication and its algebraic neighbourhood, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Elastic-Degenerate String Matching via Fast 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, An improved combinatorial algorithm for Boolean matrix multiplication, Pushdown reachability with constant treewidth, Bounds for graph regularity and removal lemmas, Linear-space data structures for range mode query in arrays, A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs, Grothendieck-Type Inequalities in Combinatorial Optimization, A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma