کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418466 | 681673 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Proof of Berge’s path partition conjecture for k≥λ−3k≥λ−3
ترجمه فارسی عنوان
اثبات حدس پارتیشن مسیر برگ برای k≥λ-3k≥λ-3
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار جهت؛ پارتیشن مسیر؛ حدس پارتیشن مسیر برگ
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let DD be a digraph. A path partition of DD is called kk-optimal if the sum of the kk-norms of its paths is minimal. The k-norm of a path PP is min(|V(P)|,k)min(|V(P)|,k). Berge’s path partition conjecture claims that for every kk-optimal path partition PP there are kk disjoint stable sets orthogonal to PP. For general digraphs the conjecture has been proven for k=1,2,λ−1,λk=1,2,λ−1,λ, where λλ is the length of a longest path in the digraph. In this paper we prove the conjecture for λ−2λ−2 and λ−3λ−3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 137–143
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 137–143
نویسندگان
Dávid Herskovics,