File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Minimum Manhattan network is NP-complete

TitleMinimum Manhattan network is NP-complete
Authors
Keywords3-SAT
Minimum manhattan network
NP-complete
Issue Date2009
PublisherAssociation for Computer Machinary.
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 How to Cite?
Abstract
A 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.
Persistent Identifierhttp://hdl.handle.net/10722/61163
ISBN
ISI Accession Number ID
References

 

Author Affiliations
  1. The University of Hong Kong
  2. Fudan University
DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorGuo, Zen_HK
dc.contributor.authorSun, Hen_HK
dc.date.accessioned2010-07-13T03:32:17Z-
dc.date.available2010-07-13T03:32:17Z-
dc.date.issued2009en_HK
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-402en_HK
dc.identifier.isbn978-1-60558-501-7-
dc.identifier.urihttp://hdl.handle.net/10722/61163-
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.en_HK
dc.languageengen_HK
dc.publisherAssociation for Computer Machinary.-
dc.relation.ispartofProceedings of the Annual Symposium on Computational Geometryen_HK
dc.subject3-SATen_HK
dc.subjectMinimum manhattan networken_HK
dc.subjectNP-completeen_HK
dc.titleMinimum Manhattan network is NP-completeen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1145/1542362.1542429en_HK
dc.identifier.scopuseid_2-s2.0-70849110991en_HK
dc.identifier.hkuros166445en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70849110991&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage393en_HK
dc.identifier.epage402en_HK
dc.identifier.isiWOS:000267982900053-
dc.publisher.placeUnited States-
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.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridGuo, Z=24316668900en_HK
dc.identifier.scopusauthoridSun, H=14619833800en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats