Title

Fast Algorithms For Maintaining Shortest Paths In Outerplanar And Planar Digraphs

Abstract

We present algorithms for maintaining shortest path information in dynamic outerplanar digraphs with sublogarithmlc query time. By choosing appropriate parameters we achieve continuous trade-offs between the preprocessing, query, and update times. Our data structure is based on a recursive separator decomposition of the graph and it encodes the shortest paths between the members of a properly chosen subset of vertices. We apply this result to construct improved shortest path algorithms for dynamic planar digraphs.

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

965

Number of Pages

191-200

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/3-540-60249-6_51

Socpus ID

84947911170 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS