Subcubic equivalences between path, matrix, and triangle problems
From MaRDI portal
Recommendations
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- From circuit complexity to faster all-pairs shortest paths
- Faster all-pairs shortest paths via circuit complexity
- scientific article; zbMATH DE number 1256679
Cited in
(92)- Tight bounds for reachability problems on one-counter and pushdown systems
- Detecting and enumerating small induced subgraphs in c-closed graphs
- Maximum matching in almost linear time on graphs of bounded clique-width
- Equivalence classes and conditional hardness in massively parallel computations
- Finding the largest triangle in a graph in expected quadratic time
- Algorithms and conditional lower bounds for planning problems
- Efficiently correcting matrix products
- Bulk-robust combinatorial optimization
- A note on the complexity of computing the number of reachable vertices in a digraph
- Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
- Bisection of bounded treewidth graphs by convolutions
- Improved bounds for rectangular monotone min-plus product and applications
- An experimental study on approximating k shortest simple paths
- Efficiently correcting matrix products
- scientific article; zbMATH DE number 5899282 (Why is no real title available?)
- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
- scientific article; zbMATH DE number 1256679 (Why is no real title available?)
- Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
- Towards hardness of approximation for polynomial time problems
- Conditional hardness for sensitivity problems
- Lower bounds for tropical circuits and dynamic programs
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
- From circuit complexity to faster all-pairs shortest paths
- Bisection of bounded treewidth graphs by convolutions
- Triangles and girth in disk graphs and transmission graphs
- Faster algorithms for all-pairs bounded min-cuts
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Improving TSP tours using dynamic programming over tree decompositions
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- Improved output-sensitive quantum algorithms for Boolean matrix multiplication
- Graph classes and forbidden patterns on three vertices
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- The diameter of AT‐free graphs
- scientific article; zbMATH DE number 7765381 (Why is no real title available?)
- 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
- 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
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- A new deterministic algorithm for fully dynamic all-pairs shortest paths
- Tight conditional lower bounds for vertex connectivity problems
- Faster combinatorial \(k\)-clique algorithms
- Finding the \(k\) shortest simple paths: time and space trade-offs
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- Finding and counting small tournaments in large tournaments
- Finer-grained reductions in fine-grained hardness of approximation
- Fitting metrics and ultrametrics with minimum disagreements
- Near optimal algorithm for the directed single source replacement paths problem
- Simplifying and unifying replacement paths algorithms in weighted directed graphs
- On the fine-grained complexity of parity problems
- Complexity of linear operators
- Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
- Fast approximate counting of cycles
- Finer-grained reductions in fine-grained hardness of approximation
- Applications of random algebraic constructions to hardness of approximation
- Deterministic 3SUM-hardness
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- Tensor ranks and the fine-grained complexity of dynamic programming
- Enumeration algorithms for conjunctive queries with projection
- Fast algorithms for energy games in special cases
- K-shortest simple paths using biobjective path search
- Obstructions to faster diameter computation: asteroidal sets
- Computing minimum weight cycle in the CONGEST model
- k-shortest simple paths in bounded treewidth graphs
- New bounds for the number of lightest cycles in undirected graphs
- Restorable shortest path tiebreaking for edge-faulty graphs
- Fine-grained complexity of regular path queries
- 3sum and related problems in fine-grained complexity (invited talk)
- Two algorithms for shortest-paths problems in edge-weighted directed graphs
- Fine-grained hardness for edit distance to a fixed sequence
- Approximation algorithms for min-distance problems in DAGs
- Faster monotone min-plus product, range mode, and single source replacement paths
- Fully dynamic algorithms for minimum weight cycle and related problems
- From donkeys to kings in tournaments
- Removing the log factor from (,+)-products on bounded range integer matrices
- A nearly linear time construction of approximate single-source distance sensitivity oracles
- Improved algorithms for perfect graphs and odd holes
- Faster combinatorial k-clique algorithms
- Improved girth approximation in weighted undirected graphs
- Linear time subsequence and supersequence regex matching
- Computing oriented spanners and their dilation
- Bounded weighted edit distance: dynamic algorithms and matching lower bounds
- Non-Boolean OMv: one more reason to believe lower bounds for dynamic problems
- On the quantum time complexity of divide and conquer
- Undirected 3-fault replacement path in nearly cubic time
- Into the square: on the complexity of some quadratic-time solvable problems
This page was built for publication: Subcubic equivalences between path, matrix, and triangle problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625648)
