@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",
}