Dynamic algorithms for shortest paths in planar graphs

DOI10.1016/0304-3975(93)90328-QzbMath0783.68092OpenAlexW1967389135MaRDI QIDQ685367

Esteban Feuerstein, Alberto Marchetti-Spaccamela

Publication date: 17 October 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90328-q

zbMATH Keywords

planar networkmaintaining shortest pathsmaintaining the maximum flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Dynamic programming (90C39)

Related Items (6)

Semi-dynamic shortest paths and breadth-first search in digraphs ⋮ Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs ⋮ Shortest path queries in digraphs of small treewidth ⋮ Semi-dynamic breadth-first search in digraphs ⋮ Unnamed Item ⋮ Lifelong planning \(\text{A}^*\)

Cites Work

• A note on two problems in connexion with graphs
• Parallel concepts in graph theory
• Improved algorithms for dynamic shortest paths
• Incremental convex planarity testing
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• Incremental algorithms for minimal length paths
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Dynamic algorithms for shortest paths in planar graphs