Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs

M. M. Halldórsson, J. Radhakrishnan

Rannsóknarafurð: Framlag til fræðitímaritsGreinritrýni

143 Tilvitnanir (Scopus)

Útdráttur

The minimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of (Δ + 2)/3 for approximating independent sets in graphs with degree bounded by Δ. The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turán's bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved (2d̄ + 3)/5 performance ratio on graphs with average degree d̄, improving on the previous best (d̄ + 1)/2 of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy.

Upprunalegt tungumálEnska
Síður (frá-til)145-163
Síðufjöldi19
FræðitímaritAlgorithmica (New York)
Bindi18
Númer tölublaðs1
DOI
ÚtgáfustaðaÚtgefið - maí 1997

Fingerprint

Sökktu þér í rannsóknarefni „Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs“. Saman myndar þetta einstakt fingrafar.

Vitna í þetta