| Title | A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs |
| Authors | Andrzej Lingas, Dzmitry Sledneu |
| Alternative Location | http://dx.doi.org/10.1007/9..., Restricted Access |
| Publication | SOFSEM 2012: Theory and Practice of Computer Science (Lecture Notes in Computer Science) |
| Year | 2012 |
| Volume | 7147 |
| Pages | 373 - 384 |
| Document type | Conference paper |
| Conference name | 38th Conference on Current Trends in Theory and Practice of Computer Science |
| Conference Date | JAN 21-27, 2012 |
| Conference Location | Spindlevur Mlyn, CZECH REPUBLIC |
| Status | Published |
| Quality controlled | Yes |
| Language | eng |
| Publisher | Springer |
| Abstract English | 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)). |
| ISBN/ISSN/Other | ISSN: 0302-9743 ISBN: 978-3-642-27659-0 |
Questions: webmaster
Last update: 2013-04-11
Centre for Mathematical Sciences, Box 118, SE-22100, Lund. Telefon: +46 46-222 00 00 (vx)