Document Open Access Logo

A Fine-grained Analysis of a Simple Independent Set Algorithm

Authors Joachim Kneis, Alexander Langer, Peter Rossmanith

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2009.2326.pdf
  • Filesize: 120 kB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Exact Algorithms
  • Independent Set
  • Computer-aided Proof

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

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.

Cite As Get BibTex

Joachim Kneis, Alexander Langer, and Peter Rossmanith. A Fine-grained Analysis of a Simple Independent Set Algorithm. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 287-298, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2326

Author Details

Joachim Kneis
Alexander Langer
Peter Rossmanith
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact