The Potential of Greed for Independence - Publikacja - MOST Wiedzy

Wyszukiwarka

The Potential of Greed for Independence

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

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 122 razy

Publikacje, które mogą cię zainteresować

Meta Tagi