Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
verfasst von : Andrzej Lingas, Dzmitry Sledneu
Erschienen in: SOFSEM 2012: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of computing all-pairs shortest paths in a directed graph with non-negative real weights assigned to vertices.
For an
n
×
n
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 non-negative real weights and adjacency matrix
A
G
can be solved by a combinatorial randomized algorithm in time
$$\widetilde{O}(n^{2}\sqrt{n + \min\{MWT(A_G), MWT(A_G^t)\}})$$
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.
We also conclude that the all-pairs shortest path problem for vertex-weighted uniform disk graphs induced by point sets of bounded density within a unit square can be solved in time
$\widetilde{O}(n^{2.75})$
.