An $O^*(1.0821^n)$-Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3

Davis Issac; Ragesh Jaiswal

paper

An $O^{*} (1.082 1^{n})$ -Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3

arXiv:1308.1351

Abstract

We give an $O^{*} (1.082 1^{n})$ -time, polynomial space algorithm for computing Maximum Independent Set in graphs with bounded degree 3. This improves all the previous running time bounds known for the problem.

arXiv commentWhile working on an updated version, we observed a bug in one of the cases of our extensive case analysis. We are withdrawing this paper while we work to fix the bug. We will add an updated version once we manage to fix the bug

An O∗(1.0821n)-Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3

Abstract

An $O^{*} (1.082 1^{n})$ -Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3