@inproceedings{871ae381388343b99e6d8545ccb37e00,
title = "A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs",
abstract = "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 x 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(1). (O) over tilde (n(2)root 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 (O) over tilde (n(2.75)).",
author = "Andrzej Lingas and Dzmitry Sledneu",
year = "2012",
doi = "10.1007/978-3-642-27660-6_31",
language = "English",
isbn = "978-3-642-27659-0",
volume = "7147",
publisher = "Springer",
pages = "373--384",
booktitle = "SOFSEM 2012: Theory and Practice of Computer Science/Lecture Notes in Computer Science",
address = "Germany",
note = "38th Conference on Current Trends in Theory and Practice of Computer Science ; Conference date: 21-01-2012 Through 27-01-2012",
}