Wyszukiwarka
Abstrakt
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.
Cytowania
-
1 1
CrossRef
-
0
Web of Science
-
1 5
Scopus
Autorzy (4)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF GRAPH THEORY
nr 71,
strony 245 - 259,
ISSN: 0364-9024 - Język:
- angielski
- Rok wydania:
- 2012
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1002/jgt.20644
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 128 razy