Shortest path computations in source-deplanarized graphs

DOI10.1016/0020-0190(93)90227-ZMaRDI QIDQ685480zbMATH OpenOpenAlexFDO

Authors Greg N. Frederickson, Susanne E. Hambrusch, Hung-Yi Tu

Publication date 17 October 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90227-z

zbMATH Keywords

planar graphshortest path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
• Faster shortest-path algorithms for planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Faster shortest-path algorithms for planar graphs
• Multiple-source shortest paths in planar graphs

Cites work

• A framework for 1-D compaction with forbidden region avoidance
• A mixed-integer linear programming problem which is efficiently solvable
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 219245 (Why is no real title available?)

Cited in

(3)

• Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
• Finding a shortest non-zero path in group-labeled graphs via permanent computation
• Shortest beer path queries in outerplanar graphs

This page was built for publication: Shortest path computations in source-deplanarized graphs

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