کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419960 683877 2013 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Arc-disjoint paths and trees in 2-regular digraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Arc-disjoint paths and trees in 2-regular digraphs
چکیده انگلیسی

An out-branching (in-branching) Bs+(Bs−) in a digraph DD is a connected spanning subdigraph of DD in which every vertex x≠sx≠s has precisely one arc entering (leaving) it and ss has no arcs entering (leaving) it. We settle the complexity of the following two problems:
• Given a 2-regular digraph DD, decide whether it contains two arc-disjoint branchings Bu+, Bv−.
• Given a 2-regular digraph DD, decide whether it contains an out-branching Bu+ such that DD remains connected after removing the arcs of Bu+. Both problems are NP-complete for general digraphs (Bang-Jensen (1991) [1], Bang-Jensen and Yeo (2012) [7]). We prove that the first problem remains NP-complete for 2-regular digraphs, whereas the second problem turns out to be polynomial when we do not prescribe the root in advance. The complexity when the root is prescribed in advance is still open. We also prove that, for 2-regular digraphs, the second problem is in fact equivalent to deciding whether DD contains two arc-disjoint out-branchings.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 16–17, November 2013, Pages 2724–2730
نویسندگان
, ,