Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/70742
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 | 2011 | - |
dc.identifier.citation | Proceedings of the 3rd International Conference on Computer Research and Development, 11-13 March, 2011, Shanghai: pp.150-154 | - |
dc.identifier.isbn | 9781612848372 | - |
dc.identifier.uri | http://hdl.handle.net/2440/70742 | - |
dc.description.abstract | The min-min problem of finding a disjointpath pair with the length of the shorter path minimized is known to be NP-complete and admits no K-approximation for any K > 1 in the general case [1]. In this paper, we show that Bhatia et al [2]’s NP-complete proof, a claim of correction to Xu et al’s proof [1], for the edge-disjoint minmin problem in undirected graphs is incorrect by giving a counter example that is an unsatisfiable 3SAT instance but classified as a satisfiable 3SAT instance in Bhatia et al’s proof [2]. We then give a correct proof of NP-completeness of this problem in undirected graphs. | - |
dc.description.statementofresponsibility | Longkun Guo and Hong Shen | - |
dc.language.iso | en | - |
dc.publisher | IEEE | - |
dc.rights | © Copyright 2011 IEEE | - |
dc.source.uri | http://dx.doi.org/10.1109/iccrd.2011.5764102 | - |
dc.subject | Min-min problem | - |
dc.subject | NP-completeness | - |
dc.subject | strongly NP-completeness | - |
dc.subject | disjoint path pair | - |
dc.subject | MAX-2SAT. | - |
dc.title | On the complexity of the edge-disjoint min-min problem in undirected graphs | - |
dc.type | Conference paper | - |
dc.contributor.conference | International Conference on Computer Research and Development (3rd : 2011 : Shanghai) | - |
dc.identifier.doi | 10.1109/ICCRD.2011.5764102 | - |
dc.publisher.place | USA | - |
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_70742.pdf Restricted Access | Restricted Access | 124.61 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.