کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428332 686637 2007 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An improved exact algorithm for the domatic number problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
An improved exact algorithm for the domatic number problem
چکیده انگلیسی

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time n2.695 (up to polynomial factors) and in polynomial space. This result improves the previous bound of n2.8805, which is due to Björklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Δ(G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Δ(G)⩾5. Our new randomized algorithm employs Schöning's approach to constraint satisfaction problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 101, Issue 3, 14 February 2007, Pages 101-106