Back to Search Start Over

Minimum Manhattan Network is NP-Complete.

Authors :
Chin, Francis
Guo, Zeyu
Sun, He
Source :
Discrete & Computational Geometry. Jun2011, Vol. 45 Issue 4, p701-722. 22p.
Publication Year :
2011

Abstract

Given a set T of n points in ℝ, a Manhattan network on T is a graph G with the property that for each pair of points in T, G contains a rectilinear path between them of length equal to their distance in the L-metric. The minimum Manhattan network problem is to find a Manhattan network of minimum length, i.e., minimizing the total length of the line segments in the network. In this paper, we prove that the decision version of the MMN problem is strongly NP-complete, using a reduction from the well-known 3-SAT problem, which requires a number of gadgets. The gadgets have similar structures, but play different roles in simulating a 3-CNF formula. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
01795376
Volume :
45
Issue :
4
Database :
Academic Search Index
Journal :
Discrete & Computational Geometry
Publication Type :
Academic Journal
Accession number :
59983791
Full Text :
https://doi.org/10.1007/s00454-011-9342-z