File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Minimum Manhattan network is NP-complete
  • Basic View
  • Metadata View
  • XML View
TitleMinimum Manhattan network is NP-complete
 
AuthorsChin, FYL1
Guo, Z
Sun, H2
 
Keywords3-SAT
Minimum manhattan network
NP-complete
 
Issue Date2009
 
PublisherAssociation for Computer Machinary.
 
CitationThe 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), Aarhus, Denmark, 8-10 June 2009. In Proceedings of the 25th ACM SoCG, 2009, p. 393-402 [How to Cite?]
DOI: http://dx.doi.org/10.1145/1542362.1542429
 
AbstractA rectilinear path between two points p, q ε R2 is a path connecting p and q with all its line segments horizontal or vertical segments. Furthermore, a Manhattan path between p and q is a rectilinear path with its length exactly dist(p, q) := |p.x - q.x| + |p.y - q.y|. Given a set T of n points in R2, a network G is said to be a Manhattan network on T, if for all p, q ε T there exists a Manhattan path between p and q with all its line segmentsc in G. For the given point set T, the Minimum Manhattan Network (MMN) Problem is to find a Manhattan network G on T with the minimum network length. In this paper, we shall prove that the decision version of MMN is strongly NP-complete, using the 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 the 3-SAT formula. The reduction has been implemented with a computer program. © 2009 ACM.
 
ISBN978-1-60558-501-7
 
DOIhttp://dx.doi.org/10.1145/1542362.1542429
 
ISI Accession Number IDWOS:000267982900053
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChin, FYL
 
dc.contributor.authorGuo, Z
 
dc.contributor.authorSun, H
 
dc.date.accessioned2010-07-13T03:32:17Z
 
dc.date.available2010-07-13T03:32:17Z
 
dc.date.issued2009
 
dc.description.abstractA rectilinear path between two points p, q ε R2 is a path connecting p and q with all its line segments horizontal or vertical segments. Furthermore, a Manhattan path between p and q is a rectilinear path with its length exactly dist(p, q) := |p.x - q.x| + |p.y - q.y|. Given a set T of n points in R2, a network G is said to be a Manhattan network on T, if for all p, q ε T there exists a Manhattan path between p and q with all its line segmentsc in G. For the given point set T, the Minimum Manhattan Network (MMN) Problem is to find a Manhattan network G on T with the minimum network length. In this paper, we shall prove that the decision version of MMN is strongly NP-complete, using the 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 the 3-SAT formula. The reduction has been implemented with a computer program. © 2009 ACM.
 
dc.description.naturelink_to_OA_fulltext
 
dc.description.otherThe 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), Aarhus, Denmark, 8-10 June 2009. In Proceedings of the 25th ACM SoCG, 2009, p. 393-402
 
dc.identifier.citationThe 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), Aarhus, Denmark, 8-10 June 2009. In Proceedings of the 25th ACM SoCG, 2009, p. 393-402 [How to Cite?]
DOI: http://dx.doi.org/10.1145/1542362.1542429
 
dc.identifier.doihttp://dx.doi.org/10.1145/1542362.1542429
 
dc.identifier.epage402
 
dc.identifier.hkuros166445
 
dc.identifier.isbn978-1-60558-501-7
 
dc.identifier.isiWOS:000267982900053
 
dc.identifier.scopuseid_2-s2.0-70849110991
 
dc.identifier.spage393
 
dc.identifier.urihttp://hdl.handle.net/10722/61163
 
dc.languageeng
 
dc.publisherAssociation for Computer Machinary.
 
dc.publisher.placeUnited States
 
dc.relation.ispartofProceedings of the Annual Symposium on Computational Geometry
 
dc.relation.referencesReferences in Scopus
 
dc.subject3-SAT
 
dc.subjectMinimum manhattan network
 
dc.subjectNP-complete
 
dc.titleMinimum Manhattan network is NP-complete
 
dc.typeConference_Paper
 
<?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>2010-07-13T03:32:17Z</date.accessioned>
<date.available>2010-07-13T03:32:17Z</date.available>
<date.issued>2009</date.issued>
<identifier.citation>The 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), Aarhus, Denmark, 8-10 June 2009. In Proceedings of the 25th ACM SoCG, 2009, p. 393-402</identifier.citation>
<identifier.isbn>978-1-60558-501-7</identifier.isbn>
<identifier.uri>http://hdl.handle.net/10722/61163</identifier.uri>
<description.abstract>A rectilinear path between two points p, q &#949; R2 is a path connecting p and q with all its line segments horizontal or vertical segments. Furthermore, a Manhattan path between p and q is a rectilinear path with its length exactly dist(p, q) := |p.x - q.x| + |p.y - q.y|. Given a set T of n points in R2, a network G is said to be a Manhattan network on T, if for all p, q &#949; T there exists a Manhattan path between p and q with all its line segmentsc in G. For the given point set T, the Minimum Manhattan Network (MMN) Problem is to find a Manhattan network G on T with the minimum network length. In this paper, we shall prove that the decision version of MMN is strongly NP-complete, using the 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 the 3-SAT formula. The reduction has been implemented with a computer program. &#169; 2009 ACM.</description.abstract>
<language>eng</language>
<publisher>Association for Computer Machinary.</publisher>
<relation.ispartof>Proceedings of the Annual Symposium on Computational Geometry</relation.ispartof>
<subject>3-SAT</subject>
<subject>Minimum manhattan network</subject>
<subject>NP-complete</subject>
<title>Minimum Manhattan network is NP-complete</title>
<type>Conference_Paper</type>
<description.nature>link_to_OA_fulltext</description.nature>
<identifier.doi>10.1145/1542362.1542429</identifier.doi>
<identifier.scopus>eid_2-s2.0-70849110991</identifier.scopus>
<identifier.hkuros>166445</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-70849110991&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.spage>393</identifier.spage>
<identifier.epage>402</identifier.epage>
<identifier.isi>WOS:000267982900053</identifier.isi>
<publisher.place>United States</publisher.place>
<description.other>The 25th Annual ACM Symposium on Computational Geometry (SoCG 2009), Aarhus, Denmark, 8-10 June 2009. In Proceedings of the 25th ACM SoCG, 2009, p. 393-402</description.other>
<bitstream.url>http://hub.hku.hk/bitstream/10722/61163/1/re01.htm</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Fudan University