Please use this identifier to cite or link to this item:
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
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
polynomial-time algorithm
shortest path
disjoint path
Rights: © 2011 IEEE
DOI: 10.1109/PAAP.2011.15
Published version:
Appears in Collections:Aurora harvest
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access317.25 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.