Dynamic algorithms for shortest paths in planar graphs

DOI10.1016/0304-3975(93)90328-QzbMATH Open0783.68092OpenAlexW1967389135MaRDI QIDQ685367FDOQ685367

Authors E. 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)

Recommendations

• scientific article; zbMATH DE number 219245
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• On-line and dynamic algorithms for shortest path problems
• A fully dynamic approximation scheme for shortest paths in planar graphs
• Improved algorithms for dynamic shortest paths

Cites work

• scientific article; zbMATH DE number 432745 (Why is no real title available?)
• scientific article; zbMATH DE number 3900809 (Why is no real title available?)
• scientific article; zbMATH DE number 3907787 (Why is no real title available?)
• scientific article; zbMATH DE number 177843 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A note on two problems in connexion with graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Improved algorithms for dynamic shortest paths
• Incremental algorithms for minimal length paths
• Incremental convex planarity testing
• Parallel concepts in graph theory

Cited in

(28)

• Semi-dynamic shortest paths and breadth-first search in digraphs
• Shortest path queries in digraphs of small treewidth
• Algorithmic techniques for maintaining shortest routes in dynamic networks
• On-line and dynamic algorithms for shortest path problems
• Improved algorithms for dynamic shortest paths
• On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
• Multiple-source shortest paths in planar graphs
• Semi-dynamic breadth-first search in digraphs
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Planar graphs, negative weight edges, shortest paths, and near linear time
• A special case the of dynamization problem for least cost paths
• Improved bounds for shortest paths in dense distance graphs
• Algorithms -- ESA '93. 1st annual European symposium Bad Honnef, Germany, September 30 -- October 2, 1993. Proceedings
• Lifelong planning \(\text{A}^*\)
• Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
• A fully dynamic algorithm for planar
• Dynamic expression trees
• Faster shortest-path algorithms for planar graphs
• Dynamic shortest paths containers
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
• scientific article; zbMATH DE number 3907787 (Why is no real title available?)
• Dynamic maintenance of shortest path trees in simple polygons
• Incremental algorithms for minimal length paths
• scientific article; zbMATH DE number 3900809 (Why is no real title available?)
• Dynamic multi-level overlay graphs for shortest paths
• scientific article; zbMATH DE number 219245 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685367)