Title

On-Line And Dynamic Algorithms For Shortest Path Problems

Abstract

We describe Mgorithms for finding shortest paths and distances in a planar 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. Our data structures can be updated after any such change in only polylogarithmic time, while a single-pair query is answered in sublinear time. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem.

Publication Date

1-1-1995

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

900

Number of Pages

193-204

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/3-540-59042-0_73

Socpus ID

84947706935 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84947706935

This document is currently not available here.

Share

COinS