کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430601 688056 2012 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding kernels or solving SAT
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Finding kernels or solving SAT
چکیده انگلیسی

We begin by offering a new, direct proof of the equivalence between the problem of the existence of kernels in digraphs, KER, and satisfiability of propositional theories, SAT, giving linear reductions in both directions. Having introduced some linear reductions of the input graph, we present new algorithms for KER, with variations utilizing solvers of boolean equations. In the worst case, the algorithms try all assignments to either a feedback vertex set, F, or a set of nodes E touching only all even cycles. Hence KER is fixed parameter tractable not only in the size of F, as observed earlier, but also in the size of E  . A slight modification of these algorithms leads to a branch and bound algorithm for KER which is virtually identical to the DPLL algorithm for SAT. This suggests deeper analogies between the two problems and the probable scenario of KER research facing the challenges known from the work on SAT. The algorithm gives also the upper bound O⁎(1.427|G|)O⁎(1.427|G|) on the time complexity of general KER and O⁎(1.286|G|)O⁎(1.286|G|) of KER for oriented graphs, where |G||G| is the number of vertices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 10, January 2012, Pages 146–164
نویسندگان
, ,