Finding maximum independent sets in sparse and general graphs

Abstract

a fvg); fvg [ SparseFindMIS(G \\Gamma fvg \\Gamma N(v))) end Figure 1: An algorithm that runs in time 2 0:114e on e-edge graphs function FindMIS(G) begin if G contains at most 5n=2 edges then return SparseFindMIS(G) if G contains an edge fu; vg such that N(u) ae N(v) [ fvg then return FindMIS(G \\Gamma fvg) let d be the maximum degree of any vertex in G (* so d 6 *) if d 8 then let v be a degree-d vertex return max(FindMIS(G \\Gamm