File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Minimum Manhattan Network is NP-Complete
  • 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
2013 Impact Factor: 0.606
 
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 FieldValue
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
2013 Impact Factor: 0.606
 
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
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chin, FYL</contributor.author>
<contributor.author>Guo, Z</contributor.author>
<contributor.author>Sun, H</contributor.author>
<date.accessioned>2012-02-21T05:44:22Z</date.accessioned>
<date.available>2012-02-21T05:44:22Z</date.available>
<date.issued>2011</date.issued>
<identifier.citation>Discrete And Computational Geometry, 2011, v. 45 n. 4, p. 701-722</identifier.citation>
<identifier.issn>0179-5376</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/145068</identifier.uri>
<description.abstract>Given a set T of n points in &#8477; 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. &#169; 2011 The Author(s).</description.abstract>
<language>Eng</language>
<publisher>Springer New York LLC. The Journal&apos;s web site is located at http://link.springer.de/link/service/journals/00454/index.htm</publisher>
<relation.ispartof>Discrete and Computational Geometry</relation.ispartof>
<rights>The Author(s)</rights>
<rights>Creative Commons: Attribution 3.0 Hong Kong License</rights>
<subject>3-SAT</subject>
<subject>Minimum Manhattan networks</subject>
<subject>NP-completeness</subject>
<title>Minimum Manhattan Network is NP-Complete</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4551/resserv?sid=springerlink&amp;genre=article&amp;atitle=Minimum Manhattan Network is NP-Complete&amp;title=Discrete &amp; Computational Geometry&amp;issn=01795376&amp;date=2011-06-01&amp;volume=45&amp;issue=4&amp; spage=701&amp;authors=Francis Y. L. Chin, Zeyu Guo, He Sun</identifier.openurl>
<description.nature>published_or_final_version</description.nature>
<identifier.doi>10.1007/s00454-011-9342-z</identifier.doi>
<identifier.scopus>eid_2-s2.0-79954630704</identifier.scopus>
<identifier.hkuros>196148</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-79954630704&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>45</identifier.volume>
<identifier.issue>4</identifier.issue>
<identifier.spage>701</identifier.spage>
<identifier.epage>722</identifier.epage>
<identifier.eissn>1432-0444</identifier.eissn>
<identifier.isi>WOS:000289521700005</identifier.isi>
<publisher.place>United States</publisher.place>
<description.other>Springer Open Choice, 21 Feb 2012</description.other>
<identifier.citeulike>9085312</identifier.citeulike>
<bitstream.url>http://hub.hku.hk/bitstream/10722/145068/1/fulltext.pdf</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Fudan University