Advanced

A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs

Lingas, Andrzej LU and Sledneu, Dzmitry LU (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.373-384
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... (More)
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)). (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
1611-3349
0302-9743
ISBN
978-3-642-27659-0
DOI
10.1007/978-3-642-27660-6_31
language
English
LU publication?
yes
id
871ae381-3883-43b9-9e6d-8545ccb37e00 (old id 3147433)
date added to LUP
2012-11-21 15:21:08
date last changed
2017-01-01 03:48:02
@inproceedings{871ae381-3883-43b9-9e6d-8545ccb37e00,
  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       = {Lingas, Andrzej and Sledneu, Dzmitry},
  booktitle    = {SOFSEM 2012: Theory and Practice of Computer Science/Lecture Notes in Computer Science},
  isbn         = {978-3-642-27659-0},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {373--384},
  publisher    = {Springer},
  title        = {A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs},
  url          = {http://dx.doi.org/10.1007/978-3-642-27660-6_31},
  volume       = {7147},
  year         = {2012},
}