Hardness of finding two edge-disjoint Min-Min paths in digraphs
Files
(Restricted Access)
Date
2011
Authors
Guo, L.
Shen, H.
Editors
Atallah, M.
Li, X.Y.
Zhu, B.
Li, X.Y.
Zhu, B.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Lecture Notes in Artificial Intelligence, 2011 / Atallah, M., Li, X.Y., Zhu, B. (ed./s), vol.6681, pp.300-307
Statement of Responsibility
Longkun Guo and Hong Shen
Conference Name
Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM) (28 May 2011 - 31 May 2011 : Jinhua, China)
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).
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© Spinger-Verlag