**Conference Paper:**Minimum Manhattan network is NP-complete

Title | Minimum Manhattan network is NP-complete |
---|---|

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

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?] DOI: http://dx.doi.org/10.1145/1542362.1542429 |

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

ISBN | 978-1-60558-501-7 |

DOI | http://dx.doi.org/10.1145/1542362.1542429 |

ISI Accession Number ID | WOS:000267982900053 |

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 | 2010-07-13T03:32:17Z |

dc.date.available | 2010-07-13T03:32:17Z |

dc.date.issued | 2009 |

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

dc.description.nature | link_to_OA_fulltext |

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.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?] DOI: http://dx.doi.org/10.1145/1542362.1542429 |

dc.identifier.doi | http://dx.doi.org/10.1145/1542362.1542429 |

dc.identifier.epage | 402 |

dc.identifier.hkuros | 166445 |

dc.identifier.isbn | 978-1-60558-501-7 |

dc.identifier.isi | WOS:000267982900053 |

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

dc.identifier.spage | 393 |

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

dc.language | eng |

dc.publisher | Association for Computer Machinary. |

dc.publisher.place | United States |

dc.relation.ispartof | Proceedings of the Annual Symposium on Computational Geometry |

dc.relation.references | References in Scopus |

dc.subject | 3-SAT |

dc.subject | Minimum manhattan network |

dc.subject | NP-complete |

dc.title | Minimum Manhattan network is NP-complete |

dc.type | Conference_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 ε 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.</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&selection=ref&src=s&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

- The University of Hong Kong
- Fudan University