کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4665580 1633818 2015 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Disjoint paths in tournaments
ترجمه فارسی عنوان
مسیرهای جداگانه در مسابقات
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات (عمومی)
چکیده انگلیسی

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
نویسندگان
, , ,