文章基本信息

标题：A Fine-grained Analysis of a Simple Independent Set Algorithm
本地全文：下载
作者：Joachim Kneis ; Alexander Langer ; Peter Rossmanith 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：4
页码：287-298
DOI：10.4230/LIPIcs.FSTTCS.2009.2326
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present a simple exact algorithm for the \is\ problem with a runtime bounded by $O(\rt^n \poly(n))$. This bound is obtained by, firstly, applying a new branching rule and, secondly, by a distinct, computer-aided case analysis. The new branching rule uses the concept of satellites and has previously only been used in an algorithm for sparse graphs. The computer-aided case analysis allows us to capture the behavior of our algorithm in more detail than in a traditional analysis. The main purpose of this paper is to demonstrate how a very simple algorithm can outperform more complicated ones if the right analysis of its running time is performed.
关键词：Exact Algorithms; Independent Set; Computer-aided Proof