Minimum Manhattan network is NP-complete

DOI10.1007/S00454-011-9342-ZMaRDI QIDQ540439zbMATH OpenOpenAlexFDO

Authors Francis Y. L. Chin, Zeyu Guo, He Sun

Publication date 3 June 2011

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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)

Recommendations

• Minimum Manhattan network is NP-complete
• The transitive minimum Manhattan subnetwork problem in 3 dimensions
• A fixed-parameter algorithm for the minimum Manhattan network problem
• The Minimal Manhattan Network Problem in Three Dimensions
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem

Cites work

• scientific article; zbMATH DE number 1979512 (Why is no real title available?)
• A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem
• A catalog of Hanan grid problems
• A rounding algorithm for approximating minimum Manhattan networks
• Algorithms and Computation
• Approximating a minimum Manhattan network
• 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
• The minimum Manhattan network problem: Approximations and exact solutions

Cited in

(11)

• Linear-size planar Manhattan network for convex point sets
• scientific article; zbMATH DE number 1332659 (Why is no real title available?)
• On minimum generalized Manhattan connections
• Approximating the generalized minimum Manhattan network problem
• A fixed-parameter algorithm for the minimum Manhattan network problem
• The transitive minimum Manhattan subnetwork problem in 3 dimensions
• Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm
• Minimum Manhattan network is NP-complete
• 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

This page was built for publication: Minimum Manhattan network is NP-complete

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