The potential of greed for independence

The well‐known lower bound on the independence number of a graph due to Caro (Technical Report, Tel‐Aviv University, 1979) and Wei (Technical Memorandum, TM 81 ‐ 11217 ‐ 9, Bell Laboratories, 1981) can be established as a performance guarantee of two natural and simple greedy algorithms or of a simp...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2012-11, Vol.71 (3), p.245-259
Main Authors: Borowiecki, Piotr, Göring, Frank, Harant, Jochen, Rautenbach, Dieter
Format: Article
Language:English
Subjects:
greedy algorithm
independence
stability
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The well‐known lower bound on the independence number of a graph due to Caro (Technical Report, Tel‐Aviv University, 1979) and Wei (Technical Memorandum, TM 81 ‐ 11217 ‐ 9, Bell Laboratories, 1981) can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so‐called potential functions pG: V(G)→ℕ0 defined on the vertex set of a graph G for which suitably modified versions of the greedy algorithms applied to G yield independent sets I with . We provide examples of such potentials, which lead to bounds improving the bound due to Caro and Wei. Furthermore, suitably adapting the randomized algorithm we give a short proof of Thiele's lower bound on the independence number of a hypergraph (T. Thiele, J Graph Theory 30 (1999), 213–221).
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.20644