کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4665580 | 1633818 | 2015 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Disjoint paths in tournaments
ترجمه فارسی عنوان
مسیرهای جداگانه در مسابقات
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار، مسابقات، مسیریابی برنامه نویسی دینامیک، مسیرهای متفرق شده
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات (عمومی)
چکیده انگلیسی
Given k pairs of vertices (si,ti)(si,ti)(1≤i≤k)(1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from sisi to titi for 1≤i≤k1≤i≤k? This is NP-complete in general digraphs, even for k=2k=2[2], but for k=2k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 270, 22 January 2015, Pages 582–597
Journal: Advances in Mathematics - Volume 270, 22 January 2015, Pages 582–597
نویسندگان
Maria Chudnovsky, Alex Scott, Paul Seymour,