On the complexity of the edge-disjoint min-min problem in planar digraphs

Longkun Guo; Hong Shen

doi:10.1016/j.tcs.2011.12.009

On the complexity of the edge-disjoint min-min problem in planar digraphs

Longkun Guo
, Hong Shen

研究成果: Article › 同行評審

7 引文斯高帕斯（Scopus）

摘要

The min-min problem of finding a disjoint path pair with the length of the shorter path minimized is known to be NP-complete (Xu et al., 2006) [1]. In this paper, we prove that in planar digraphs the edge-disjoint min-min problem remains NP-complete and admits no K-approximation for any K>1 unless P=NP. As a by-product, we show that this problem remains NP-complete even when all edge costs are equal (i.e., stronglyNP-complete). To our knowledge, this is the first NP-completeness proof for the edge-disjoint min-min problem in planar digraphs.

原文	English
頁（從 - 到）	58-63
頁數	6
期刊	Theoretical Computer Science
卷	432
DOIs	https://doi.org/10.1016/j.tcs.2011.12.009
出版狀態	Published - 11 5月 2012
對外發佈	是

存取文件

10.1016/j.tcs.2011.12.009

其它文件與鏈接

Link to publication in Scopus

引用此

@article{5d0dbfe2dc42414d919cf19cb94319f3,

title = "On the complexity of the edge-disjoint min-min problem in planar digraphs",

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 (Xu et al., 2006) [1]. In this paper, we prove that in planar digraphs the edge-disjoint min-min problem remains NP-complete and admits no K-approximation for any K>1 unless P=NP. As a by-product, we show that this problem remains NP-complete even when all edge costs are equal (i.e., stronglyNP-complete). To our knowledge, this is the first NP-completeness proof for the edge-disjoint min-min problem in planar digraphs.",

keywords = "Disjoint path, Inapproximability, Min-min problem, NP-complete, Planar digraph",

author = "Longkun Guo and Hong Shen",

note = "Funding Information: ✩ This work was partially supported by the {\textquoteleft}{\textquoteleft}100 Talents{\textquoteright}{\textquoteright} Project of Chinese Academy of China, National Science Foundation of China grant \#61170232 and∗ Correspondingauthorat:SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,China.Tel.:+61883035592.FundamentalResearchFundsfortheCentralUniversities.ThecorrespondingauthorisHongShen. E-mail address: [email protected] (H. Shen).",

year = "2012",

month = may,

day = "11",

doi = "10.1016/j.tcs.2011.12.009",

language = "English",

volume = "432",

pages = "58--63",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - On the complexity of the edge-disjoint min-min problem in planar digraphs

AU - Guo, Longkun

AU - Shen, Hong

N1 - Funding Information: ✩ This work was partially supported by the ‘‘100 Talents’’ Project of Chinese Academy of China, National Science Foundation of China grant #61170232 and∗ Correspondingauthorat:SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,China.Tel.:+61883035592.FundamentalResearchFundsfortheCentralUniversities.ThecorrespondingauthorisHongShen. E-mail address: [email protected] (H. Shen).

PY - 2012/5/11

Y1 - 2012/5/11

N2 - The min-min problem of finding a disjoint path pair with the length of the shorter path minimized is known to be NP-complete (Xu et al., 2006) [1]. In this paper, we prove that in planar digraphs the edge-disjoint min-min problem remains NP-complete and admits no K-approximation for any K>1 unless P=NP. As a by-product, we show that this problem remains NP-complete even when all edge costs are equal (i.e., stronglyNP-complete). To our knowledge, this is the first NP-completeness proof for the edge-disjoint min-min problem in planar digraphs.

AB - The min-min problem of finding a disjoint path pair with the length of the shorter path minimized is known to be NP-complete (Xu et al., 2006) [1]. In this paper, we prove that in planar digraphs the edge-disjoint min-min problem remains NP-complete and admits no K-approximation for any K>1 unless P=NP. As a by-product, we show that this problem remains NP-complete even when all edge costs are equal (i.e., stronglyNP-complete). To our knowledge, this is the first NP-completeness proof for the edge-disjoint min-min problem in planar digraphs.

KW - Disjoint path

KW - Inapproximability

KW - Min-min problem

KW - NP-complete

KW - Planar digraph

UR - https://www.scopus.com/pages/publications/84859527092

U2 - 10.1016/j.tcs.2011.12.009

DO - 10.1016/j.tcs.2011.12.009

M3 - Article

AN - SCOPUS:84859527092

SN - 0304-3975

VL - 432

SP - 58

EP - 63

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

On the complexity of the edge-disjoint min-min problem in planar digraphs

摘要

存取文件

其它文件與鏈接

指紋

引用此