Improved algorithms for dynamic shortest paths
UNSPECIFIED. (2000) Improved algorithms for dynamic shortest paths. ALGORITHMICA, 28 (4). pp. 367-389. ISSN 0178-4617Full text not available from this repository.
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|
|Number of Pages:||23|
|Page Range:||pp. 367-389|
Actions (login required)