کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433769 689623 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding good 2-partitions of digraphs I. Hereditary properties
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Finding good 2-partitions of digraphs I. Hereditary properties
چکیده انگلیسی

We study the complexity of deciding whether a given digraph D   has a vertex-partition into two disjoint subdigraphs with given structural properties. Let HH and EE denote the following two sets of natural properties of digraphs: HH = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and EE = {strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k1,k2k1,k2, whether a given digraph has a vertex partition into two digraphs D1,D2D1,D2 such that |V(Di)|≥ki|V(Di)|≥ki and DiDi has property PiPi for i=1,2i=1,2 when P1∈HP1∈H and P2∈H∪EP2∈H∪E. We also classify the complexity of the same problems when restricted to strongly connected digraphs.The complexity of the 2-partition problems where both P1P1 and P2P2 are in EE is determined in the companion paper [2].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 636, 11 July 2016, Pages 85–94
نویسندگان
, ,