کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434860 | 689815 | 2012 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of the edge-disjoint min–min problem in planar digraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 432, 11 May 2012, Pages 58-63
Journal: Theoretical Computer Science - Volume 432, 11 May 2012, Pages 58-63