Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs

DOI10.1007/3-540-60249-6_51MaRDI QIDQ5055890zbMATH OpenOpenAlexFDO

Authors Hristo N. Djidjev, Grammati Pantziou, Christos Zaroliagis

Publication date 9 December 2022

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60249-6_51

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Improved algorithms for dynamic shortest paths
• Dynamic algorithms for shortest paths in planar graphs
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• scientific article; zbMATH DE number 219245
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms

Cites work

• Dynamic algorithms for shortest paths in planar graphs
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On-line and dynamic algorithms for shortest path problems
• Planar graph decomposition and all pairs shortest paths
• Shortest path queries in digraphs of small treewidth

Cited in

(7)

• Improved algorithms for dynamic shortest paths
• A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs
• On-line and dynamic algorithms for shortest path problems
• Faster shortest-path algorithms for planar graphs
• Shortest beer path queries in outerplanar graphs
• Efficient algorithms for shortest path queries in planar digraphs
• Dynamic maintenance of planar digraphs, with applications

This page was built for publication: Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs

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