Name
Abstract | ||
|---|---|---|
The well-known lower bound on the independence number of a graph due to Caro (Technical Report, Tel-Aviv University, 1979) and Wei (Technical Memorandum, TM 81 - 11217 - 9, Bell Laboratories, 1981) 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 pG: V(G)→ℕ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 *. 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 (T. Thiele, J Graph Theory 30 (1999), 213–221). © 2012 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1002/jgt.20644 | Journal of Graph Theory |
Keywords | Field | DocType |
randomized algorithm,technical report,simple greedy algorithm,technical memorandum,t. thiele,greedy algorithm,graph g,simple randomized algorithm,independence number,vertex weight,independence,stability | Graph theory,Randomized algorithm,Combinatorics,Vertex (geometry),Upper and lower bounds,Generalization,Hypergraph,Greedy algorithm,Mathematics,Technical report | Journal |
Volume | Issue | ISSN |
71 | 3 | 0364-9024 |
Citations | PageRank | References |
9 | 0.62 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Piotr Borowiecki | 1 | 43 | 8.12 |
| Frank Göring | 2 | 53 | 9.00 |
| Jochen Harant | 3 | 217 | 30.62 |
| Dieter Rautenbach | 4 | 946 | 138.87 |