Publications Repository - Gdańsk University of Technology

The well-known lower bound on the independence number of a graph due to Caro and Wei 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 p(G) : V(G) -> N_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 |I|>=Sum_{uinV(G)} 1/(p(G)+1). 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.

Authors

• dr hab. inż. Piotr Borowiecki link open in new tab ,
• Frank Goering,
• Jochen Harant,
• Dieter Rautenbach