Keywords (1)

Minimum Manhattan Network is NP-Complete

Minimum Manhattan Network is NP-Complete,10.1007/s00454-011-9342-z,Discrete & Computational Geometry,Francis Y. L. Chin,Zeyu Guo,He Sun

Minimum Manhattan Network is NP-Complete  
BibTex | RIS | RefWorks Download
Given a set T of n points in ℝ2, 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 1-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.
Journal: Discrete & Computational Geometry - DCG , vol. 45, no. 4, pp. 701-722, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.