The potential of greed for independence

DOI10.1002/JGT.20644MaRDI QIDQ4650180zbMATH OpenOpenAlexWikidataFDO

Authors 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 algorithmGrundy potentialindependent setlocally treelike graphspotential functionweighting vertices

Mathematics Subject Classification ID

Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• New potential functions for greedy independence and coloring
• GreedyMAX-type algorithms for the maximum independent set problem
• A note on greedy algorithms for the maximum weighted independent set problem
• scientific article; zbMATH DE number 1405697
• A lower bound on the independence number of a graph in terms of degrees

Cites work

• A lower bound on the independence number of arbitrary hypergraphs
• A probabilistic lower bound on the independence number of graphs
• GreedyMAX-type algorithms for the maximum independent set problem
• Improved lower bounds on k‐independence
• Inequalities for the Grundy chromatic number of graphs
• Lower bounds on the independence number in terms of the degrees
• On the equality of the partial Grundy and upper ochromatic numbers of graphs
• On the Grundy number of a graph
• Small transversals in hypergraphs

Cited in

(17)

• A note on greedy algorithms for the maximum weighted independent set problem
• New potential functions for greedy independence and coloring
• Remarks on dynamic monopolies with given average thresholds
• MAX for \(k\)-independence in multigraphs
• Transversals and independence in linear hypergraphs with maximum degree two
• Partitions of graphs into small and large sets
• Independence in uniform linear triangle-free hypergraphs
• The Fano plane and the strong independence ratio in hypergraphs of maximum degree 3
• A lower bound on the independence number of a graph in terms of degrees and local clique sizes
• GreedyMAX-type algorithms for the maximum independent set problem
• New bounds on the independence number of connected graphs
• 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
• A lower bound on the independence number of a graph in terms of degrees
• Improving the Caro-Wei bound and applications to Turán stability

Describes a project that uses

Uses Software

• GreedyMAX

This page was built for publication: The potential of greed for independence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4650180)