کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875609 1441975 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
One-to-one disjoint path covers in digraphs
ترجمه فارسی عنوان
مسیر تک نفره ای که به هم متصل نیست در مسیر دیفرانسیل قرار می گیرد
کلمات کلیدی
نمودارهای هدایت شده، پوشش مسیر متفرق شده، حداقل نیمه درجه،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A one-to-one k-disjoint directed path cover (k-DDPC for short) of a digraph D is a set of k disjoint directed paths joining source with sink that cover all the vertices of the digraph. Let δ0(D):=min{δ+(D),δ−(D)} be the minimum semi-degree of D. We show that every digraph D of sufficiently large order n with δ0(D)⩾⌈(n+k+1)/2⌉ contains a one-to-one k-DDPC for any given one distinct source-sink. The undirected version and a Ore-type degree conditions of this result was proved earlier [1].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 714, 1 March 2018, Pages 27-35
نویسندگان
, , ,