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
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 19 May 2014
10:45
60 Minutes
E1 4
024
Saarbrücken
Abstract
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.
Contact
Jennifer Gerling
1800
--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.
Jennifer Gerling, 05/15/2014 11:33 -- Created document.