All pairs shortest paths using bridging sets and rectangular matrix multiplication
From MaRDI portal
Publication:3455533
DOI10.1145/567112.567114zbMath1326.05157arXivcs/0008011OpenAlexW2049500052WikidataQ56170982 ScholiaQ56170982MaRDI QIDQ3455533
Publication date: 7 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0008011
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (69)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs ⋮ A new approach to all-pairs shortest paths on real-weighted graphs ⋮ Faster algorithms for finding lowest common ancestors in directed acyclic graphs ⋮ A survey of the all-pairs shortest paths problem and its variants in graphs ⋮ A Task-Scheduling Approach for Efficient Sparse Symmetric Matrix-Vector Multiplication on a GPU ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Extreme Witnesses and Their Applications ⋮ Multi-agent differential graphical games: online adaptive learning solution for synchronization with optimality ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs ⋮ Unnamed Item ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs ⋮ Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound ⋮ Algebraic theory on shortest paths for all flows ⋮ Approximate shortest paths in weighted graphs ⋮ A shortest cycle for each vertex of a graph ⋮ Faster algorithms for all-pairs small stretch distances in weighted graphs ⋮ On bounded leg shortest paths problems ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Unnamed Item ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model ⋮ An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. ⋮ Improved distance sensitivity oracles with subcubic preprocessing time ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ On minimum witnesses for Boolean matrix multiplication ⋮ Approximating the minimum cycle mean ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Algebraic methods in the congested clique ⋮ Algebraic Theory on Shortest Paths for All Flows ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximating Shortest Paths in Graphs ⋮ Two bilinear \((3\times3)\)-matrix multiplication algorithms of complexity 25 ⋮ All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time ⋮ Extreme witnesses and their applications ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Unnamed Item ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Unnamed Item ⋮ Faster Algorithms for All Pairs Non-Decreasing Paths Problem ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ Computational study on planar dominating set problem ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Incremental distance products via faulty shortest paths ⋮ Vertex labeling and routing for Farey-type symmetrically-structured graphs ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Variations on the bottleneck paths problem ⋮ Unnamed Item ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Dominance Product and High-Dimensional Closest Pair under L_infty ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
This page was built for publication: All pairs shortest paths using bridging sets and rectangular matrix multiplication
