The Potential of Greed for Independence - Publication - Bridge of Knowledge

Search

The Potential of Greed for Independence

Abstract

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.

Citations

  • 1 1

    CrossRef

  • 0

    Web of Science

  • 1 5

    Scopus

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
JOURNAL OF GRAPH THEORY no. 71, pages 245 - 259,
ISSN: 0364-9024
Language:
English
Publication year:
2012
Bibliographic description:
Borowiecki P., Goering F., Harant J., Rautenbach D.: The Potential of Greed for Independence// JOURNAL OF GRAPH THEORY. -Vol. 71, nr. iss. 3 (2012), s.245-259
DOI:
Digital Object Identifier (open in new tab) 10.1002/jgt.20644
Verified by:
Gdańsk University of Technology

seen 122 times

Recommended for you

Meta Tags