A polynomial algorithm for the vertex disjoint Min-Min problem in planar graphs
Files
(Restricted Access)
Date
2011
Authors
Guo, L.
Shen, H.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the Fourth International Symposium on Parallel Architectures, Algorithms and Programming (PAAP), held in Tianjin, 9-11 December, 2011: pp.47-51
Statement of Responsibility
Longkun Guo and Hong Shen
Conference Name
International Symposium on Parallel Architectures, Algorithms and Programming (4th : 2011 : Tianjin)
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/).
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2011 IEEE