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
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGuo, L.-
dc.contributor.authorShen, H.-
dc.contributor.editorAtallah, M.-
dc.contributor.editorLi, X.Y.-
dc.contributor.editorZhu, B.-
dc.date.issued2011-
dc.identifier.citationLecture Notes in Artificial Intelligence, 2011 / Atallah, M., Li, X.Y., Zhu, B. (ed./s), vol.6681, pp.300-307-
dc.identifier.isbn9783642212031-
dc.identifier.issn0302-9743-
dc.identifier.issn1611-3349-
dc.identifier.urihttp://hdl.handle.net/2440/71087-
dc.description.abstractThe 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).-
dc.description.statementofresponsibilityLongkun Guo and Hong Shen-
dc.language.isoen-
dc.publisherSpringer-Verlag Berlin-
dc.relation.ispartofseriesLecture Notes in Computer Science-
dc.rights© Spinger-Verlag-
dc.source.urihttp://dx.doi.org/10.1007/978-3-642-21204-8_32-
dc.subjectMin-Min problem-
dc.subjectplanar digraph-
dc.subjectNP-completeness-
dc.subjectdisjoint path-
dc.subjectinapproximability-
dc.titleHardness of finding two edge-disjoint Min-Min paths in digraphs-
dc.typeConference paper-
dc.contributor.conferenceJoint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM) (28 May 2011 - 31 May 2011 : Jinhua, China)-
dc.identifier.doi10.1007/978-3-642-21204-8_32-
dc.publisher.placeHeidelberger Platz 3 Berlin Germany D-14197-
pubs.publication-statusPublished-
dc.identifier.orcidShen, H. [0000-0002-3663-6591] [0000-0003-0649-0648]-
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 simple item record


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