Regularity Lemmas and Combinatorial Algorithms
From MaRDI portal
Publication:5171230
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)
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