Search results for: INDEPPENDENCE

• The Potential of Greed for Independence

  Publication

  • P. Borowiecki
  • F. Goering
  • J. Harant
  • D. Rautenbach

  - JOURNAL OF GRAPH THEORY - Year 2012

  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...

  Full text to download in external service