کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875565 | 1441970 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Out-degree reducing partitions of digraphs
ترجمه فارسی عنوان
پارتیشن های دیفرانسیونی را کاهش می دهد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let k be a fixed integer. We determine the complexity of finding a p-partition (V1,â¦,Vp) of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by Vi, (1â¤iâ¤p) is at least k smaller than the maximum out-degree of D. We show that this problem is polynomial-time solvable when pâ¥2k and NP-complete otherwise. The result for k=1 and p=2 answers a question posed in [3]. We also determine, for all fixed non-negative integers k1,k2,p, the complexity of deciding whether a given digraph of maximum out-degree p has a 2-partition (V1,V2) such that the digraph induced by Vi has maximum out-degree at most ki for iâ[2]. It follows from this characterization that the problem of deciding whether a digraph has a 2-partition (V1,V2) such that each vertex vâVi has at least as many neighbours in the set V3âi as in Vi, for i=1,2 is NP-complete. This solves a problem from [6] on majority colourings.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 719, 6 April 2018, Pages 64-72
Journal: Theoretical Computer Science - Volume 719, 6 April 2018, Pages 64-72
نویسندگان
J. Bang-Jensen, S. Bessy, F. Havet, A. Yeo,