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_31zbMATH Open1302.05194arXiv1111.6519OpenAlexW3124258952MaRDI QIDQ2891383FDOQ2891383

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)

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})$.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient determination of the transitive closure of a directed graph
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Title not available (Why is that?)
• Matrix multiplication via arithmetic progressions
• Title not available (Why is that?)
• Fast recognition of pushdown automaton and context-free languages
• Regularity Lemmas and Combinatorial Algorithms
• Fast rectangular matrix multiplication and applications
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Title not available (Why is that?)
• On the exponent of all pairs shortest path problem
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Title not available (Why is that?)
• Fly cheaply: On the minimum fuel consumption problem
• Approximate Distance Queries in Disk Graphs
• Title not available (Why is that?)
• An improved bound on Boolean matrix multiplication for highly clustered data.
• 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
• Title not available (Why is that?)

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)