Search
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
Authors (4)
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 126 times