Campus Event Calendar

Event Entry

What and Who

Better Exact Algorithm for Maximum Independent Set Problem in Graphs with Bounded Degree 3

Davis Issac
Indian Institute of Technology Delhi
PhD Application Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Public Audience

Date, Time and Location

Monday, 19 May 2014
60 Minutes
E1 4


Maximum Independent Set Problem is one of the most extensively studied NP-hard problem. The problem, when limited to degree-3 bounded graphs, remains NP-hard. Over the years, researchers have come up with more and more efficient algorithms for the Maximum Independent Set Problem in degree-3 bounded graphs. The best known algorithm so far is the O*(1.0836n) algorithm by Xiao and Nagamuchi. In this work, we present a new algorithm which runs in O*(1.0821n) time and uses polynomial space.

Like most of the previous algorithms for this problem, the basic structure of our algorithm is recursive backtracking with case analysis. The main idea that we use is that by removing small cycles we can make the branchings more efficient. We remove the cycles that have a length of at most 6. The main core of the algorithm deals with how to remove these cycles efficiently. The idea of removing small cycles gives a more natural way of doing the case analysis for the problem.


Jennifer Gerling
--email hidden
passcode not visible
logged in users only

Jennifer Gerling, 05/15/2014 11:33
Jennifer Gerling, 05/15/2014 11:33 -- Created document.