File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Minimum Manhattan Network is NP-Complete

TitleMinimum Manhattan Network is NP-Complete
Authors
Chin, FYLGuo, ZSun, H
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
Citation
Discrete 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).
Persistent Identifierhttp://hdl.handle.net/10722/145068
ISSN
0179-5376
2021 Impact Factor: 0.639
2020 SCImago Journal Rankings: 0.645
ISI Accession Number ID
WOS: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.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorGuo, Zen_HK
dc.contributor.authorSun, Hen_HK
dc.date.accessioned2012-02-21T05:44:22Z-
dc.date.available2012-02-21T05:44:22Z-
dc.date.issued2011en_HK
dc.identifier.citationDiscrete And Computational Geometry, 2011, v. 45 n. 4, p. 701-722en_HK
dc.identifier.issn0179-5376en_HK
dc.identifier.urihttp://hdl.handle.net/10722/145068-
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).en_HK
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htmen_HK
dc.relation.ispartofDiscrete and Computational Geometryen_HK
dc.rightsThe Author(s)en_US
dc.subject3-SATen_HK
dc.subjectMinimum Manhattan networksen_HK
dc.subjectNP-completenessen_HK
dc.titleMinimum Manhattan Network is NP-Completeen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4551/resserv?sid=springerlink&genre=article&atitle=Minimum Manhattan Network is NP-Complete&title=Discrete & Computational Geometry&issn=01795376&date=2011-06-01&volume=45&issue=4& spage=701&authors=Francis Y. L. Chin, Zeyu Guo, He Sunen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturepublished_or_final_versionen_US
dc.identifier.doi10.1007/s00454-011-9342-zen_HK
dc.identifier.scopuseid_2-s2.0-79954630704en_HK
dc.identifier.hkuros196148-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79954630704&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume45en_HK
dc.identifier.issue4en_HK
dc.identifier.spage701en_HK
dc.identifier.epage722en_HK
dc.identifier.eissn1432-0444en_US
dc.identifier.isiWOS:000289521700005-
dc.publisher.placeUnited Statesen_HK
dc.description.otherSpringer Open Choice, 21 Feb 2012en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridGuo, Z=24316668900en_HK
dc.identifier.scopusauthoridSun, H=36024325800en_HK
dc.identifier.citeulike9085312-
dc.identifier.issnl0179-5376-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats