Minimum Manhattan network is NP-complete
From MaRDI portal
Publication:540439
DOI10.1007/s00454-011-9342-zzbMath1228.05185OpenAlexW4241180678MaRDI QIDQ540439
Zeyu Guo, He Sun, Francis Y. L. Chin
Publication date: 3 June 2011
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-011-9342-z
Related Items
Linear-size planar Manhattan network for convex point sets, On minimum generalized Manhattan connections, Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm, Approximating the generalized minimum Manhattan network problem, Approximating minimum Manhattan networks in higher dimensions, Exact algorithms for the order picking problem, Dynamic programming approach to the generalized minimum Manhattan network problem, Optimal realizations of two-dimensional, totally-decomposable metrics
Cites Work
- Unnamed Item
- Unnamed Item
- The minimum Manhattan network problem: Approximations and exact solutions
- A rounding algorithm for approximating minimum Manhattan networks
- A catalog of Hanan grid problems
- A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
- Greedy Construction of 2-Approximation Minimum Manhattan Network
- The Minimal Manhattan Network Problem in Three Dimensions
- The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
- Algorithms and Computation