2009-08: Satellites and Mirrors for Solving Independent Set on Sparse Graphs
2 Apr
2009
2 Apr
'09
2:15 p.m.
The following technical report is available from http://aib.informatik.rwth-aachen.de: Satellites and Mirrors for Solving Independent Set on Sparse Graphs Joachim Kneis, Alexander Langer AIB 2009-08 We study the well-known Maximum Independent Set (MIS) problem and introduce the notion of satellites of a node. Branching on nodes with satellites is extremely simple. Nevertheless, satellites can be used to overcome a couple of hard cases in previous algorithms. Together with the notion of mirrors, introduced by Fomin, Grandoni, and Kratsch, they can be used to solve MIS in time bounded by O^*(1.1928^{m-n}), which is O^*(1.0922^n) for cubic graphs. This improves over previous results for sparse graphs.
5742
Age (days ago)
5742
Last active (days ago)
0 comments
1 participants
participants (1)
-
Carsten Fuhs