The potential of greed for independence
From MaRDI portal
Publication:4650180
DOI10.1002/jgt.20644zbMath1254.05135OpenAlexW1489463487WikidataQ62043613 ScholiaQ62043613MaRDI QIDQ4650180
Piotr Borowiecki, Frank Göring, Dieter Rautenbach, Jochen Harant
Publication date: 23 November 2012
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20644
greedy algorithmindependent setpotential functionGrundy potentiallocally treelike graphsweighting vertices
Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (13)
Transversals and independence in linear hypergraphs with maximum degree two ⋮ Independence in uniform linear triangle-free hypergraphs ⋮ A lower bound on the independence number of a graph in terms of degrees and local clique sizes ⋮ New bounds on the independence number of connected graphs ⋮ Partitions of graphs into small and large sets ⋮ An improved lower bound on the independence number of a graph ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ Bounds on the independence number of a graph in terms of order, size and maximum degree ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ New potential functions for greedy independence and coloring ⋮ Remarks on dynamic monopolies with given average thresholds ⋮ The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3 ⋮ MAX for \(k\)-independence in multigraphs
Uses Software
Cites Work
- Small transversals in hypergraphs
- A probabilistic lower bound on the independence number of graphs
- On the equality of the partial Grundy and upper ochromatic numbers of graphs
- Lower bounds on the independence number in terms of the degrees
- Inequalities for the Grundy chromatic number of graphs
- On the Grundy Number of a Graph
- GreedyMAX-type Algorithms for the Maximum Independent Set Problem
- Improved lower bounds on k‐independence
- A lower bound on the independence number of arbitrary hypergraphs
This page was built for publication: The potential of greed for independence