A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs

DOI10.1007/978-3-642-27660-6_31MaRDI QIDQ2891383zbMATH OpenOpenAlexFDO

Authors Dzmitry Sledneu, Andrzej Lingas

Publication date 15 June 2012

Published in SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.6519

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Analysis of algorithms (68W40) Paths and cycles (05C38)

Abstract: We consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. For an $nimesn$ 0-1 matrix $C,$ let $K_C$ be the complete weighted graph on the rows of $C$ where the weight of an edge between two rows is equal to their Hamming distance. Let $MWT(C)$ be the weight of a minimum weight spanning tree of $K_C.$ We show that the all-pairs shortest path problem for a directed graph $G$ on $n$ vertices with nonnegative real weights and adjacency matrix $A_G$ can be solved by a combinatorial randomized algorithm in time ${\displaystyle }$widetilde{O}(n^{2}sqrt {n + min{MWT(A_G), MWT(A_G^t)}})${\displaystyle }$ As a corollary, we conclude that the transitive closure of a directed graph $G$ can be computed by a combinatorial randomized algorithm in the aforementioned time. $widetildeO(n^{2}sqrtn+minMWT(A_G),MWT(A_G^t))$ We also conclude that the all-pairs shortest path problem for uniform disk graphs, with nonnegative real vertex weights, induced by point sets of bounded density within a unit square can be solved in time $widetildeO(n^{2.75})$.

Recommendations

• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
• All-pairs shortest paths in \(O(n^2)\) time with high probability
• scientific article; zbMATH DE number 6861957

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1256679 (Why is no real title available?)
• scientific article; zbMATH DE number 686998 (Why is no real title available?)
• scientific article; zbMATH DE number 1979525 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 1830739 (Why is no real title available?)
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• An improved bound on Boolean matrix multiplication for highly clustered data.
• Approximate Distance Queries in Disk Graphs
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Efficient determination of the transitive closure of a directed graph
• Fast recognition of pushdown automaton and context-free languages
• Fast rectangular matrix multiplication and applications
• Fly cheaply: On the minimum fuel consumption problem
• Matrix multiplication via arithmetic progressions
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• On the exponent of all pairs shortest path problem
• Regularity Lemmas and Combinatorial Algorithms
• Subquadratic approximation algorithms for clustering problems in high dimensional spaces

Cited in

(5)

• Efficient parameterized algorithms for computing all-pairs shortest paths
• 3D rectangulations and geometric matrix multiplication
• All-pairs bottleneck paths in vertex weighted graphs
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• scientific article; zbMATH DE number 6861957 (Why is no real title available?)

This page was built for publication: A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2891383)