A shortest-path algorithm for Manhattan graphs

DOI10.1016/0020-0190(94)90049-3MaRDI QIDQ1313705zbMATH OpenOpenAlexFDO

Authors Kanchana Kanchanasut

Publication date 24 February 1994

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

Full work available at URL https://doi.org/10.1016/0020-0190(94)90049-3

zbMATH Keywords

shortest pathManhattan graph

Mathematics Subject Classification ID

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

Recommendations

• An O(n log n) Manhattan path algorithm
• Greedy construction of 2-approximate minimum Manhattan networks
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• scientific article; zbMATH DE number 1979512
• Finding Shortest Paths With Computational Geometry

Cites work

• A note on two problems in connexion with graphs
• A shortest path algorithm for grid graphs
• Shortest paths in Euclidean graphs
• Some Variations of Lee's Algorithm

Cited in

(7)

• The two‐median problem on Manhattan meshes
• A connectivity graph generation approach for Manhattan path calculation in detailed facility layout
• Functional pearl: nearest shelters in Manhattan
• Shortest path distance in Manhattan Poisson line Cox process
• Finding a manhattan path and related problems
• Finding Shortest Paths With Computational Geometry
• An O(n log n) Manhattan path algorithm

This page was built for publication: A shortest-path algorithm for Manhattan graphs

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