A Combinatorial Algorithm for AllPairs Shortest Paths in Directed VertexWeighted Graphs with Applications to Disc Graphs
(2012) 38th Conference on Current Trends in Theory and Practice of Computer Science In SOFSEM 2012: Theory and Practice of Computer Science/Lecture Notes in Computer Science 7147. p.373384 Abstract
 We consider the problem of computing allpairs shortest paths in a directed graph with nonnegative real weights assigned to vertices. For an n x n 0  1 matrix C, let KC 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 KC. We show that the allpairs 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(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... (More)
 We consider the problem of computing allpairs shortest paths in a directed graph with nonnegative real weights assigned to vertices. For an n x n 0  1 matrix C, let KC 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 KC. We show that the allpairs 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(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 allpairs shortest path problem for vertexweighted 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)). (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/3147433
 author
 Lingas, Andrzej ^{LU} and Sledneu, Dzmitry ^{LU}
 organization
 publishing date
 2012
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 SOFSEM 2012: Theory and Practice of Computer Science/Lecture Notes in Computer Science
 volume
 7147
 pages
 373  384
 publisher
 Springer
 conference name
 38th Conference on Current Trends in Theory and Practice of Computer Science
 external identifiers

 wos:000307258500031
 scopus:84856025481
 ISSN
 16113349
 03029743
 ISBN
 9783642276590
 DOI
 10.1007/9783642276606_31
 language
 English
 LU publication?
 yes
 id
 871ae381388343b99e6d8545ccb37e00 (old id 3147433)
 date added to LUP
 20121121 15:21:08
 date last changed
 20170101 03:48:02
@inproceedings{871ae381388343b99e6d8545ccb37e00, abstract = {We consider the problem of computing allpairs shortest paths in a directed graph with nonnegative real weights assigned to vertices. For an n x n 0  1 matrix C, let KC 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 KC. We show that the allpairs 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(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 allpairs shortest path problem for vertexweighted 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 = {Lingas, Andrzej and Sledneu, Dzmitry}, booktitle = {SOFSEM 2012: Theory and Practice of Computer Science/Lecture Notes in Computer Science}, isbn = {9783642276590}, issn = {16113349}, language = {eng}, pages = {373384}, publisher = {Springer}, title = {A Combinatorial Algorithm for AllPairs Shortest Paths in Directed VertexWeighted Graphs with Applications to Disc Graphs}, url = {http://dx.doi.org/10.1007/9783642276606_31}, volume = {7147}, year = {2012}, }