کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428652 686857 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dominating set based exact algorithms for 3-coloring
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Dominating set based exact algorithms for 3-coloring
چکیده انگلیسی

We show that the 3-colorability problem can be solved in O(n1.296)O(1.296n) time on any n  -vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in 2o(n)2o(n) time for graphs having minimum degree at least ω(n)ω(n) where ω(n)ω(n) is any function which goes to ∞. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a 2o(n)2o(n) time nor a 2o(m)2o(m) time algorithm is possible (m   denotes the number of edges) for 3-colorability unless Exponential Time Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(n1.2535)O(1.2535n) time.

Research highlights
► This paper provides faster algorithms for 3-colorability of graphs with lower bounds on minimum degree.
► Also, the existence of sub-exponential time algorithms are shown to be unlikely if the lower bound on the minimum degree is a constant.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 6, 15 February 2011, Pages 251–255
نویسندگان
, ,