A polynomial algorithm for the vertex disjoint Min-Min problem in planar graphs

Longkun Guo, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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

Original languageEnglish
Title of host publicationProceedings - 2011 4th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP 2011
Pages47-51
Number of pages5
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event2011 4th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP 2011 - Tianjin, China
Duration: 9 Dec 201111 Dec 2011

Publication series

NameProceedings - 2011 4th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP 2011

Conference

Conference2011 4th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP 2011
Country/TerritoryChina
CityTianjin
Period9/12/1111/12/11

Keywords

  • Disjoint path
  • Min-Min problem
  • NP-hard
  • Planar graphs
  • Polynomial-time algorithm
  • Shortest path

Fingerprint

Dive into the research topics of 'A polynomial algorithm for the vertex disjoint Min-Min problem in planar graphs'. Together they form a unique fingerprint.

Cite this