Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/71580
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | A polynomial algorithm for the vertex disjoint Min-Min problem in planar graphs |
Author: | Guo, L. Shen, H. |
Citation: | Proceedings of the Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP), held in Tianjin, 9-11 December, 2011: pp.47-51 |
Publisher: | IEEE |
Publisher Place: | USA |
Issue Date: | 2011 |
ISBN: | 9781457718083 |
Conference Name: | International Symposium on Parallel Architectures, Algorithms and Programming (4th : 2011 : Tianjin) |
Statement of Responsibility: | Longkun Guo and Hong Shen |
Abstract: | The Min-Min problem of finding a disjoint-path pair with the length of the shorter path minimized is known to be NP-hard in general graphs. However, it remains an open problem whether the Min-Min problem is NP-hard in some special graph such as planar graphs. In this paper, for an st-outerplanar graph G = (V,E) which is a special planar graph that can be drawn in the plane with source vertex s and destination vertex t belong to the unbounded face of the drawing, we show that the vertex disjoint Min-Min problem is polynomial solvable therein by presenting an algorithm with a time complexity of O(/E/ + /V/log/V/). |
Keywords: | Min-Min problem planar graphs NP-hard polynomial-time algorithm shortest path disjoint path |
Rights: | © 2011 IEEE |
DOI: | 10.1109/PAAP.2011.15 |
Published version: | http://dx.doi.org/10.1109/paap.2011.15 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_71580.pdf Restricted Access | Restricted Access | 317.25 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.