Minimum Manhattan network is NP-complete

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

zbMATH Keywords

3-SAT\(\mathbf{NP}\)-completenessminimum Manhattan networks

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12)

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