Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
AIB 2009-08: Satellites and Mirrors for Solving Independent Set on Sparse Graphs
2 views
Skip to first unread message
Carsten Fuhs
Apr 7, 2009, 5:53:25 PM4/7/09
to
The following technical report is available from
http://aib.informatik.rwth-aachen.de:
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.
0 new messages