کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328702 | 684868 | 2005 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding complementary cycles in locally semicomplete digraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
It is well known that the problem of deciding whether a given digraph has a k-cycle factor for some constant k (i.e. a collection of k disjoint cycles that cover all vertices of the digraph) is NP-complete as this is a generalization of the Hamilton cycle problem. In this paper, we show that for the class of locally semicomplete digraphs the existence of a 2-cycle factor can be decided, and a 2-cycle factor found if it exists, in time O(n3), where n is the order of the digraph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 245-256
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 245-256
نویسندگان
Jørgen Bang-Jensen, Morten Hegner Nielsen,