کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435567 689915 2016 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover
چکیده انگلیسی

We investigate the gap between theory and practice for exact branching algorithms. In theory, branch-and-reduce algorithms currently have the best time complexity for numerous important problems. On the other hand, in practice, state-of-the-art methods are based on different approaches, and the empirical efficiency of such theoretical algorithms has seldom been investigated probably because they are seemingly inefficient because of the plethora of complex reduction rules. In this paper, we design a branch-and-reduce algorithm for the vertex cover problem using the techniques developed for theoretical algorithms and compare its practical performance with other state-of-the-art empirical methods. The results indicate that branch-and-reduce algorithms are actually quite practical and competitive with other state-of-the-art approaches for several kinds of instances, thus showing the practical impact of theoretical research on branching algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 1, 4 January 2016, Pages 211–225
نویسندگان
, ,