Subcubic Equivalences Between Path, Matrix, and Triangle Problems
From MaRDI portal
Publication:4625648
DOI10.1145/3186893zbMath1426.68133OpenAlexW2892948282WikidataQ129321976 ScholiaQ129321976MaRDI QIDQ4625648
Virginia Vassilevska Williams, R. Ryan Williams
Publication date: 25 February 2019
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3186893
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Matrices of integers (15B36) Signed and weighted graphs (05C22) Boolean and Hadamard matrices (15B34)
Related Items (44)
Equivalence classes and conditional hardness in massively parallel computations ⋮ Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs ⋮ A note on the complexity of computing the number of reachable vertices in a digraph ⋮ An improved combinatorial algorithm for Boolean matrix multiplication ⋮ Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Efficiently correcting matrix products ⋮ Efficiently Correcting Matrix Products ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ Finding the largest triangle in a graph in expected quadratic time ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ The diameter of AT‐free graphs ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Improved bounds for rectangular monotone min-plus product and applications ⋮ On the hardness of computing the edit distance of shallow trees ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ A polyhedral perspective on tropical convolutions ⋮ Shortest distances as enumeration problem ⋮ Unnamed Item ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Algorithms and conditional lower bounds for planning problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized aspects of triangle enumeration ⋮ Tight bounds for reachability problems on one-counter and pushdown systems ⋮ Bulk-robust combinatorial optimization ⋮ Detecting and enumerating small induced subgraphs in \(c\)-closed graphs ⋮ Unnamed Item ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: Subcubic Equivalences Between Path, Matrix, and Triangle Problems
