Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/78994
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Guo, L. | - |
dc.contributor.author | Shen, H. | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | Algorithmica: an international journal in computer science, 2013; 66(3):641-653 | - |
dc.identifier.issn | 0178-4617 | - |
dc.identifier.issn | 1432-0541 | - |
dc.identifier.uri | http://hdl.handle.net/2440/78994 | - |
dc.description.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. | - |
dc.description.statementofresponsibility | Longkun Guo, Hong Shen | - |
dc.language.iso | en | - |
dc.publisher | Springer-Verlag | - |
dc.rights | © Springer Science+Business Media, LLC 2012 | - |
dc.source.uri | http://dx.doi.org/10.1007/s00453-012-9656-0 | - |
dc.subject | Min-Min problem | - |
dc.subject | Planar graph | - |
dc.subject | NP-hardness | - |
dc.subject | Polynomial-time algorithm | - |
dc.subject | Shortest path | - |
dc.subject | Disjoint paths | - |
dc.title | On finding Min-Min disjoint paths | - |
dc.type | Journal article | - |
dc.identifier.doi | 10.1007/s00453-012-9656-0 | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Shen, H. [0000-0002-3663-6591] [0000-0003-0649-0648] | - |
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.