Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: On finding Min-Min disjoint paths
Author: Guo, L.
Shen, H.
Citation: Algorithmica, 2013; 66(3):641-653
Publisher: Springer-Verlag
Issue Date: 2013
ISSN: 0178-4617
Statement of
Longkun Guo, 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 and admits no K-approximation for any K>1 in the general case (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006). In this paper, we first show that Bhatia et al.’s NP-hardness proof (Bhatia et al. in J. Comb. Optim. 12:83–96, 2006), a claim of correction to Xu et al.’s proof (Xu et al. in IEEE/ACM Trans. Netw. 14:147–158, 2006), for the edge-disjoint Min-Min problem in the general undirected graphs is incorrect by giving a counter example that is an unsatisfiable 3SAT instance but classified as a satisfiable 3SAT instance in the proof of Bhatia et al. (J. Comb. Optim. 12:83–96, 2006). We then gave a correct proof of NP-hardness of this problem in undirected graphs. Finally we give a polynomial-time algorithm for the vertex disjoint Min-Min problem in planar graphs by showing that the vertex disjoint Min-Min problem is polynomially solvable in st-planar graph G=(V,E) whose corresponding auxiliary graph G(V,E∪{e(st)}) can be embedded into a plane, and a planar graph can be decomposed into several st-planar graphs whose Min-Min paths collectively contain a Min-Min disjoint-path pair between s and t in the original graph G. To the best of our knowledge, these are the first polynomial algorithms for the Min-Min problems in planar graphs.
Keywords: Min-Min problem; Planar graph; NP-hardness; Polynomial-time algorithm; Shortest path; Disjoint paths
Rights: © Springer Science+Business Media, LLC 2012
RMID: 0020128778
DOI: 10.1007/s00453-012-9656-0
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_78994.pdfRestricted Access522.8 kBAdobe PDFView/Open

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