Efficient algorithms for shortest path queries in planar digraphs

DOI10.1007/3-540-62559-3_14MaRDI QIDQ6550542zbMATH OpenFDO

Authors Hristo N. Djidjev

Publication date 5 June 2024

Full work available at URL https://doi.org/10.1007/3-540-62559-3_14

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 176745
• Fast algorithms for maintaining shortest paths in outerplanar and planar digraphs
• Multiple-source shortest paths in planar graphs
• Shortest path queries in planar graphs
• Improved algorithms for dynamic shortest paths

Cites work

• A note on two problems in connexion with graphs
• Designing networks with compact routing tables
• Dynamic algorithms for graphs with treewidth 2
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster shortest-path algorithms for planar graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 176745 (Why is no real title available?)
• scientific article; zbMATH DE number 219245 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Shortest path queries in digraphs of small treewidth

Cited in

(3)

• Shortest beer path queries in digraphs with bounded treewidth
• Almost optimal exact distance oracles for planar graphs
• Faster construction of a planar distance oracle with \(\tilde{O}(1)\) query time

This page was built for publication: Efficient algorithms for shortest path queries in planar digraphs

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