A probabilistic lower bound on the independence number of graphs
From MaRDI portal
Publication:1336674
DOI10.1016/0012-365X(93)00102-BzbMath0810.05039MaRDI QIDQ1336674
Publication date: 9 April 1995
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items
On Selkow's bound on the independence number of graphs ⋮ On vertex independence number of uniform hypergraphs ⋮ Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives ⋮ Partitions of graphs into small and large sets ⋮ Constructing test functions for global optimization using continuous formulations of graph problems ⋮ The potential of greed for independence ⋮ New potential functions for greedy independence and coloring ⋮ Simple and local independent set approximation ⋮ GreedyMAX-type Algorithms for the Maximum Independent Set Problem ⋮ A lower bound on the independence number of a graph ⋮ A note on greedy algorithms for the maximum weighted independent set problem ⋮ Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
Cites Work
