On-Line and Dynamic Algorithms for Shortest Path Problems
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Description
Abstract
We describe algorithms for finding shortest paths and distances in aplanar digraph which 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. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only O (log of n) time, where N is the number of vertices of the digraph. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our results can be extended to hold for digraphs of genus o(n).
Description
Advisor
Degree
Type
Keywords
Citation
Djidjev, Hristo N.. "On-Line and Dynamic Algorithms for Shortest Path Problems." (2005) https://hdl.handle.net/1911/96440.