Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/78994
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | On finding Min-Min disjoint paths |
Author: | Guo, L. Shen, H. |
Citation: | Algorithmica: an international journal in computer science, 2013; 66(3):641-653 |
Publisher: | Springer-Verlag |
Issue Date: | 2013 |
ISSN: | 0178-4617 1432-0541 |
Statement of Responsibility: | 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 |
DOI: | 10.1007/s00453-012-9656-0 |
Published version: | http://dx.doi.org/10.1007/s00453-012-9656-0 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_78994.pdf Restricted Access | Restricted Access | 522.8 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.