The potential of greed for independence

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

zbMATH Keywords

greedy algorithmindependent setpotential functionGrundy potentiallocally treelike graphsweighting vertices

Mathematics Subject Classification ID

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

• GreedyMAX

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