Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: On the complexity of the edge-disjoint min-min problem in undirected graphs
Author: Guo, L.
Shen, H.
Citation: Proceedings of the 3rd International Conference on Computer Research and Development, 11-13 March, 2011, Shanghai: pp.150-154
Publisher: IEEE
Publisher Place: USA
Issue Date: 2011
ISBN: 9781612848372
Conference Name: International Conference on Computer Research and Development (3rd : 2011 : Shanghai)
Statement of
Longkun Guo and Hong Shen
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.
Keywords: Min-min problem; NP-completeness; strongly NP-completeness; disjoint path pair; MAX-2SAT.
Rights: © Copyright 2011 IEEE
RMID: 0020111797
DOI: 10.1109/ICCRD.2011.5764102
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_70742.pdfRestricted Access124.61 kBAdobe PDFView/Open

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