**Article:**Minimum Manhattan Network is NP-Complete

Title | Minimum Manhattan Network is NP-Complete | ||||
---|---|---|---|---|---|

Authors | Chin, FYL1 Guo, Z2 Sun, H2 | ||||

Keywords | 3-SAT Minimum Manhattan networks NP-completeness | ||||

Issue Date | 2011 | ||||

Publisher | Springer 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 | ||||

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. © 2011 The Author(s). | ||||

ISSN | 0179-5376 2012 Impact Factor: 0.649 2012 SCImago Journal Rankings: 1.088 | ||||

DOI | http://dx.doi.org/10.1007/s00454-011-9342-z | ||||

ISI Accession Number ID | WOS:000289521700005
Funding Information: The research was in parts supported by a GRF grant in Hong Kong, HKU 7116/08E. | ||||

References | References in Scopus | ||||

DC Field | Value | ||||
---|---|---|---|---|---|

dc.contributor.author | Chin, FYL | ||||

dc.contributor.author | Guo, Z | ||||

dc.contributor.author | Sun, H | ||||

dc.date.accessioned | 2012-02-21T05:44:22Z | ||||

dc.date.available | 2012-02-21T05:44:22Z | ||||

dc.date.issued | 2011 | ||||

dc.description.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. © 2011 The Author(s). | ||||

dc.description.nature | published_or_final_version | ||||

dc.description.other | Springer Open Choice, 21 Feb 2012 | ||||

dc.identifier.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 | ||||

dc.identifier.citeulike | 9085312 | ||||

dc.identifier.doi | http://dx.doi.org/10.1007/s00454-011-9342-z | ||||

dc.identifier.eissn | 1432-0444 | ||||

dc.identifier.epage | 722 | ||||

dc.identifier.hkuros | 196148 | ||||

dc.identifier.isi | WOS:000289521700005
Funding Information: The research was in parts supported by a GRF grant in Hong Kong, HKU 7116/08E. | ||||

dc.identifier.issn | 0179-5376 2012 Impact Factor: 0.649 2012 SCImago Journal Rankings: 1.088 | ||||

dc.identifier.issue | 4 | ||||

dc.identifier.openurl | |||||

dc.identifier.scopus | eid_2-s2.0-79954630704 | ||||

dc.identifier.spage | 701 | ||||

dc.identifier.uri | http://hdl.handle.net/10722/145068 | ||||

dc.identifier.volume | 45 | ||||

dc.language | Eng | ||||

dc.publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00454/index.htm | ||||

dc.publisher.place | United States | ||||

dc.relation.ispartof | Discrete and Computational Geometry | ||||

dc.relation.references | References in Scopus | ||||

dc.rights | The Author(s) | ||||

dc.rights | Creative Commons: Attribution 3.0 Hong Kong License | ||||

dc.subject | 3-SAT | ||||

dc.subject | Minimum Manhattan networks | ||||

dc.subject | NP-completeness | ||||

dc.title | Minimum Manhattan Network is NP-Complete | ||||

dc.type | Article | ||||

<?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 ℝ 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).</description.abstract> <language>Eng</language> <publisher>Springer New York LLC. The Journal'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&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 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&selection=ref&src=s&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

- The University of Hong Kong
- Fudan University