File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1542362.1542429
- Scopus: eid_2-s2.0-70849110991
- WOS: WOS:000267982900053
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Minimum Manhattan network is NP-complete
Title | Minimum Manhattan network is NP-complete |
---|---|
Authors | |
Keywords | 3-SAT Minimum manhattan network NP-complete |
Issue Date | 2009 |
Publisher | Association 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 Identifier | http://hdl.handle.net/10722/61163 |
ISBN | |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Guo, Z | en_HK |
dc.contributor.author | Sun, H | en_HK |
dc.date.accessioned | 2010-07-13T03:32:17Z | - |
dc.date.available | 2010-07-13T03:32:17Z | - |
dc.date.issued | 2009 | en_HK |
dc.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 | en_HK |
dc.identifier.isbn | 978-1-60558-501-7 | - |
dc.identifier.uri | http://hdl.handle.net/10722/61163 | - |
dc.description.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. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Association for Computer Machinary. | - |
dc.relation.ispartof | Proceedings of the Annual Symposium on Computational Geometry | en_HK |
dc.subject | 3-SAT | en_HK |
dc.subject | Minimum manhattan network | en_HK |
dc.subject | NP-complete | en_HK |
dc.title | Minimum Manhattan network is NP-complete | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1145/1542362.1542429 | en_HK |
dc.identifier.scopus | eid_2-s2.0-70849110991 | en_HK |
dc.identifier.hkuros | 166445 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-70849110991&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 393 | en_HK |
dc.identifier.epage | 402 | en_HK |
dc.identifier.isi | WOS:000267982900053 | - |
dc.publisher.place | United States | - |
dc.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 | - |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Guo, Z=24316668900 | en_HK |
dc.identifier.scopusauthorid | Sun, H=14619833800 | en_HK |