Please use this identifier to cite or link to this item: http://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
RMID: 0020117728
DOI: 10.1109/PAAP.2011.15
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_71580.pdfRestricted Access317.25 kBAdobe PDFView/Open


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