کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656894 1632987 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Vertex-disjoint directed and undirected cycles in general digraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Vertex-disjoint directed and undirected cycles in general digraphs
چکیده انگلیسی

The dicycle transversal number  τ(D)τ(D) of a digraph D is the minimum size of a dicycle transversal of D  , i.e. a set T⊆V(D)T⊆V(D) such that D−TD−T is acyclic. We study the following problem: Given a digraph D, decide if there is a dicycle B in D and a cycle C   in its underlying undirected graph UG(D)UG(D) such that V(B)∩V(C)=∅V(B)∩V(C)=∅. It is known that there is a polynomial time algorithm for this problem when restricted to strongly connected graphs, which actually finds B, C if they exist. We generalize this to any class of digraphs D   with either τ(D)≠1τ(D)≠1 or τ(D)=1τ(D)=1 and a bounded number of dicycle transversals, and show that the problem is NPNP-complete for a special class of digraphs D   with τ(D)=1τ(D)=1 and, hence, in general.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 106, May 2014, Pages 1–14
نویسندگان
, , , ,