A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
(2012) 38th Conference on Current Trends in Theory and Practice of 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:
https://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
- host publication
- 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
- conference dates
- 2012-01-21 - 2012-01-27
- 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
- 2016-04-01 10:40:26
- date last changed
- 2024-01-06 22:18:16
@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}},
doi = {{10.1007/978-3-642-27660-6_31}},
volume = {{7147}},
year = {{2012}},
}