10.4230/LIPICS.FSTTCS.2009.2326
Kneis, Joachim
Joachim
Kneis
Langer, Alexander
Alexander
Langer
Rossmanith, Peter
Peter
Rossmanith
A Fine-grained Analysis of a Simple Independent Set Algorithm
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Article
Exact Algorithms
Independent Set
Computer-aided Proof
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
2009
2009-12-14
2009-12-14
2009-12-14
en
urn:nbn:de:0030-drops-23269
10.4230/LIPIcs.FSTTCS.2009
978-3-939897-13-2
1868-8969
10.4230/LIPIcs.FSTTCS.2009
LIPIcs, Volume 4, FSTTCS 2009
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
4
25
287
298
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Kannan, Ravi
Ravi
Kannan
Kumar, K. Narayan
K. Narayan
Kumar
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
4
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
123443 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 287-298