Minimum Manhattan Network is NP-Complete

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

Research output: Contribution to journalArticlepeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)701-722
Number of pages22
JournalDiscrete & computational geometry
Volume45
Issue number4
DOIs
Publication statusPublished - 25 Mar 2011
Event25th Annual Symposium on Computational Geometry - Aarhus, Denmark
Duration: 8 Jun 200910 Jun 2009

Fingerprint

Dive into the research topics of 'Minimum Manhattan Network is NP-Complete'. Together they form a unique fingerprint.

Cite this