Paper Info
Title
A Polynomial Algorithm for the Vertex Disjoint Min-Min Problem in Planar Graphs
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|).
Year
DOI
Venue
2011
10.1109/PAAP.2011.15
PAAP
Keywords
Field
DocType
disjoint path,np-hard,planar graphs,time complexity,destination vertex,vertex disjoint min-min problem,np-hard problem,st-outerplanar graph,special graph,polynomial algorithm,min-min problem,planar graph,special planar graph,polynomial approximation,computational complexity,open problem,shortest path,general graph,polynomial-time algorithm,graph theory,disjoint-path pair,source vertex,bismuth,face,outerplanar graph,polynomials,np hard
Discrete mathematics,Combinatorics,Outerplanar graph,Vertex (graph theory),Neighbourhood (graph theory),Vertex cover,Pathwidth,1-planar graph,Feedback vertex set,Mathematics,Planar graph
Conference
ISBN
Citations 
PageRank 
978-1-4577-1808-3
0
0.34
References 
Authors
12
2
Name
Order
Citations
PageRank
Longkun Guo165.49
Hong Shen249952.98