Minimum Manhattan network is NP-complete

DOI10.1007/S00454-011-9342-ZzbMATH Open1228.05185OpenAlexW4241180678MaRDI QIDQ540439FDOQ540439

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

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• The minimum Manhattan network problem: Approximations and exact solutions
• A rounding algorithm for approximating minimum Manhattan networks
• Approximating a minimum Manhattan network
• 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
• Title not available (Why is that?)
• The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation
• Algorithms and Computation

Cited In (11)

• Linear-size planar Manhattan network for convex point sets
• Title not available (Why is that?)
• 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)