1. Adelaide Research & Scholarship
  2. Schools and Disciplines
  3. School of Computer Science
  4. Computer Science publications
Please use this identifier to cite or link to this item: https://hdl.handle.net/2440/71087
Citations
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: Lecture Notes in Artificial Intelligence, 2011 / Atallah, M., Li, X.Y., Zhu, B. (ed./s), vol.6681, pp.300-307
Publisher: Springer-Verlag Berlin
Publisher Place: Heidelberger Platz 3 Berlin Germany D-14197
Issue Date: 2011
Series/Report no.: Lecture Notes in Computer Science
ISBN: 9783642212031
ISSN: 0302-9743
1611-3349
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)
Editor: Atallah, M.
Li, X.Y.
Zhu, B.
Statement of
Responsibility: 		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
DOI: 10.1007/978-3-642-21204-8_32
Published version: http://dx.doi.org/10.1007/978-3-642-21204-8_32
Appears in Collections:Aurora harvest 5
Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_71087.pdf
  Restricted Access		Restricted Access248.3 kBAdobe PDFView/Open
Show full item record


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