Authors: Richard Beigel

Abstract: We obtain the fastest MIS algorithms for sparse graphs and for graphs whose degree is bounded by 3 or by 4. We also obtain the fastest MIS algorithm for general graphs that runs in polynomial space, and the fastest MIS algorithm for general graphs that fits on one journal page.

Our first simple algorithm finds maximum independent sets in time

• 2^0.114e for graphs with e edges
• 2^0.171n for n-node graphs with maximum degree 3
• 2^0.228n for n-node graphs with maximum degree 4

Our second simple algorithm finds maximum independent sets in time 2^0.303n for general graphs. Our third algorithm, which uses a complicated case analysis, finds maximum independent sets in time 2^0.290n for general graphs. All of our algorithms run in polynomial space.

Space allows us to present only our first two algorithms.

Download 2-page Extended Abstract