Article: Minimum Manhattan Network is NP-Complete

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleMinimum Manhattan Network is NP-Complete
AuthorsChin, FYL1
Guo, Z2
Sun, H2
Keywords3-SAT
Minimum Manhattan networks
NP-completeness
Issue Date2011
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htm
CitationDiscrete And Computational Geometry, 2011, v. 45 n. 4, p. 701-722 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00454-011-9342-z
AbstractGiven 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. © 2011 The Author(s).
ISSN0179-5376
2011 Impact Factor: 0.938
2011 SCImago Journal Rankings: 0.060
DOIhttp://dx.doi.org/10.1007/s00454-011-9342-z
ISI Accession Number IDWOS:000289521700005
Funding AgencyGrant Number
Hong Kong, HKU7116/08E
Funding Information:

The research was in parts supported by a GRF grant in Hong Kong, HKU 7116/08E.

ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorChin, FYL
dc.contributor.authorGuo, Z
dc.contributor.authorSun, H
dc.date.accessioned2012-02-21T05:44:22Z
dc.date.available2012-02-21T05:44:22Z
dc.date.issued2011
dc.description.abstractGiven 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. © 2011 The Author(s).
dc.description.naturepublished_or_final_version
dc.description.otherSpringer Open Choice, 21 Feb 2012
dc.identifier.citationDiscrete And Computational Geometry, 2011, v. 45 n. 4, p. 701-722 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00454-011-9342-z
dc.identifier.citeulike9085312
dc.identifier.doihttp://dx.doi.org/10.1007/s00454-011-9342-z
dc.identifier.eissn1432-0444
dc.identifier.epage722
dc.identifier.hkuros196148
dc.identifier.isiWOS:000289521700005
Funding AgencyGrant Number
Hong Kong, HKU7116/08E
Funding Information:

The research was in parts supported by a GRF grant in Hong Kong, HKU 7116/08E.

dc.identifier.issn0179-5376
2011 Impact Factor: 0.938
2011 SCImago Journal Rankings: 0.060
dc.identifier.issue4
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-79954630704
dc.identifier.spage701
dc.identifier.urihttp://hdl.handle.net/10722/145068
dc.identifier.volume45
dc.languageEng
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htm
dc.publisher.placeUnited States
dc.relation.ispartofDiscrete and Computational Geometry
dc.relation.referencesReferences in Scopus
dc.rightsThe Author(s)
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
dc.subject3-SAT
dc.subjectMinimum Manhattan networks
dc.subjectNP-completeness
dc.titleMinimum Manhattan Network is NP-Complete
dc.typeArticle
Author Affiliations
  1. The University of Hong Kong
  2. Fudan University