The potential of greed for independence

Piotr Borowiecki, Frank Göring, Jochen Harant, Dieter Rautenbach

Type: Article

Publication Date: 2011-12-01

Citations: 20

DOI: https://doi.org/10.1002/jgt.20644

View Publication

Locations

Journal of Graph Theory - View

Similar Works

Action	Title	Year	Authors
+	New potential functions for greedy independence and coloring	2014	Piotr Borowiecki Dieter Rautenbach
+	Exponential Independence	2016	Simon Jäger Dieter Rautenbach
+	Exponential Independence	2016	Simon Jäger Dieter Rautenbach
+	A lower bound on the independence number of arbitrary hypergraphs	1999	Torsten Thiele
+	Exponential independence	2016	Simon Jäger Dieter Rautenbach
+ PDF Chat	Independence trees and Hamilton cycles	1998	Hajo Broersma Hilde Tuinstra
+ PDF Chat	Counting independent sets in structured graphs	2024	Matija Bucić Maria Chudnovsky Julien Codsi
+	A note on the random greedy independent set algorithm	2013	Patrick Bennett Tom Bohman
+	A note on the random greedy independent set algorithm	2013	Patrick Bennett Tom Bohman
+	A hypergraph version of the Gallai-Edmonds Theorem	2007	Matěj Stehlı́k
+	Introduction to graphs	2006	Alexander K. Hartmann Martin Weigt
+	A new lower bound on the independence number of graphs	2013	Éric Angel Romain Campigotto Christian Laforest
+	$\boldsymbol{H}$-Games Played on Vertex Sets of Random Graphs	2023	Gal Kronenberg Adva Mond Alon Naor
+ PDF Chat	Whitney's connectivity inequalities for directed hypergraphs	2021	Anahy Santiago Arguello Peter F. Stadler
+ PDF Chat	Lower bounds for the independence and<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>k</mml:mi></mml:math>-independence number of graphs using the concept of degenerate degrees	2015	Manouchehr Zaker
+	When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time	2019	Sepehr Assadi Shay Solomon
+ PDF Chat	Number of Independent Sets in Regular and Irregular Graphs: A 31 Year Journey	2024	Dev Chheda R. M. Goel Eddie Qiao
+	An Intermediate Value Theorem for Graph Parameters	2011	Narong Punnim
+	A note on the Caro-Tuza bound on the independence number of uniform hypergraphs ∗	2012	Béla Csaba Thomas A. Plick Ali Shokoufandeh
+	Preface: 17th Cologne–Twente Workshop on Graphs and Combinatorial Optimization (CTW 2019)	2021	Bodo Manthey Johann L. Hurink

Works That Cite This (14)

Action	Title	Year	Authors
+	MAX for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" id="d1e1482" altimg="si19.gif"><mml:mi>k</mml:mi></mml:math>-independence in multigraphs	2019	Nevena Francetić Sara Herke Daniel Horsley
+	The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3	2015	Michael A. Henning Christian Löwenstein
+ PDF Chat	Independence in uniform linear triangle-free hypergraphs	2016	Piotr Borowiecki Michael Gentner Christian Löwenstein Dieter Rautenbach
+	Bounds on the independence number of a graph in terms of order, size and maximum degree	2016	Nader Jafari Rad Elahe Sharifi
+	New potential functions for greedy independence and coloring	2014	Piotr Borowiecki Dieter Rautenbach
+	Partitions of graphs into small and large sets	2013	Asen Bojilov Yair Caro Adriana Hansberg Nedyalko Nenov
+	Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees	2017	Michael Gentner Dieter Rautenbach
+	On sequential heurestic methods for the maximum independent set problem	2017	Christoph Brause Ngoc C. Lê Ingo Schiermeyer
+	MAX for $k$-independence in multigraphs	2018	Nevena Francetić Sara Herke Daniel Horsley
+	New bounds on the independence number of connected graphs	2018	Nader Jafari Rad Elahe Sharifi

Works Cited by This (8)

Action	Title	Year	Authors
+	Improved lower bounds on <i>k</i>‐independence	1991	Yair Caro Źsolt Tuza
+	Lower bounds on the independence number in terms of the degrees	1983	Jerrold R. Griggs
+	A Probabilistic lower bound on the independence number of graphs	1994	Stanley M. Selkow
+	A lower bound on the independence number of arbitrary hypergraphs	1999	T. N. Thiele
+	On the equality of the partial Grundy and upper ochromatic numbers of graphs	2003	Paul Erdős Stephen T. Hedetniemi Renu Laskar Geert Prins
+	Small transversals in hypergraphs	1992	Vasek Chv�tal C. McDiarmid
+	On the Grundy Number of a Graph	2010	Frédéric Havet Leonardo Sampaio
+	A lower bound on the independence number of arbitrary hypergraphs	1999	T. N. Thiele