The Library
Improved algorithms for dynamic shortest paths
Tools
Tools
Tools
UNSPECIFIED (2000) Improved algorithms for dynamic shortest paths. ALGORITHMICA, 28 (4). pp. 367-389. ISSN 0178-4617
Full text not available from this repository.Abstract
We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n-vertex digraphs of genus O(n(1-epsilon)) for any epsilon > 0.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Journal or Publication Title: | ALGORITHMICA |
| Publisher: | SPRINGER-VERLAG |
| ISSN: | 0178-4617 |
| Date: | December 2000 |
| Volume: | 28 |
| Number: | 4 |
| Number of Pages: | 23 |
| Page Range: | pp. 367-389 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/12984 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
