کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225761 | 1701211 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Degree constrained 2-partitions of semicomplete digraphs
ترجمه فارسی عنوان
درجه 2 پارتیشن های دیجیتال نیمه کامل را محدود می کند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A 2-partition of a digraph D is a partition (V1,V2) of V(D) into two disjoint non-empty sets V1 and V2 such that V1âªV2=V(D). A semicomplete digraph is a digraph with no pair of non-adjacent vertices. We consider the complexity of deciding whether a given semicomplete digraph has a 2-partition such that each part of the partition induces a (semicomplete) digraph with some specified property. In [4] and [5] Bang-Jensen, Cohen and Havet determined the complexity of 120 such 2-partition problems for general digraphs. Several of these problems are NP-complete for general digraphs and thus it is natural to ask whether this is still the case for well-structured classes of digraphs, such as semicomplete digraphs. This is the main topic of the paper. More specifically, we consider 2-partition problems where the set of properties are minimum out-, minimum in- or minimum semi-degree. Among other results we prove the following:
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 112-123
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 112-123
نویسندگان
Jørgen Bang-Jensen, Tilde My Christiansen,