Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Hardness of finding two edge-disjoint Min-Min paths in digraphs
Author: Guo, L.
Shen, H.
Citation: 5th International Frontiers in Algorithmics Workshop and the 7th International Conference on Algorithmic Aspects in Information and Management (FAW-AAIM 2011); Lecture Notes in Computer Science, vol. 6681, 2011 / vol.6681, pp.300-307
Publisher: Springer-Verlag Berlin
Publisher Place: Heidelberger Platz 3 Berlin Germany D-14197
Issue Date: 2011
ISBN: 9783642212031
ISSN: 0302-9743
Conference Name: Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM) (28 May 2011 : Jinhua, China)
Statement of
Longkun Guo and 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-complete and no K-approximation exists for any K ≥ 1 [1]. In this paper, we give a simpler proof of this result in general digraphs. We show that this proof can be extended to the problem in planar digraphs whose complexity was unknown previously. As a by-product, we show this problem remains NP-complete even when all edge costs are equal (i.e. strongly NP-complete).
Keywords: Min-Min problem; planar digraph; NP-completeness; disjoint path; inapproximability
Rights: © Spinger-Verlag
RMID: 0020111779
DOI: 10.1007/978-3-642-21204-8_32
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_71087.pdfRestricted Access248.3 kBAdobe PDFView/Open

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