@inproceedings{b7bb2639d3c748ccbc1b506e36ffb73a,

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 |).",

keywords = "Disjoint path, Min-Min problem, NP-hard, Planar graphs, Polynomial-time algorithm, Shortest path",

author = "Longkun Guo and Hong Shen",

year = "2011",

doi = "10.1109/PAAP.2011.15",

language = "English",

isbn = "9780769545752",

series = "Proceedings - 2011 4th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP 2011",

pages = "47--51",

booktitle = "Proceedings - 2011 4th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP 2011",

note = "2011 4th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP 2011 ; Conference date: 09-12-2011 Through 11-12-2011",

}