Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2326
URN: urn:nbn:de:0030-drops-23269
URL: https://drops.dagstuhl.de/opus/volltexte/2009/2326/
Kneis, Joachim ; Langer, Alexander ; Rossmanith, Peter
A Fine-grained Analysis of a Simple Independent Set Algorithm
| pdf-format: |
|
Abstract
We present a simple exact algorithm for the \is\ problem with a runtime boundedby $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.
BibTeX - Entry
@InProceedings{kneis_et_al:LIPIcs:2009:2326,
author = {Joachim Kneis and Alexander Langer and Peter Rossmanith},
title = {{A Fine-grained Analysis of a Simple Independent Set Algorithm}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {287--298},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-13-2},
ISSN = {1868-8969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2326},
URN = {urn:nbn:de:0030-drops-23269},
doi = {10.4230/LIPIcs.FSTTCS.2009.2326},
annote = {Keywords: Exact Algorithms, Independent Set, Computer-aided Proof}
}
| Keywords: | Exact Algorithms, Independent Set, Computer-aided Proof | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science | |
| Issue date: | 2009 | |
| Date of publication: | 14.12.2009 |
