Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections

DOI10.1017/S0963548309990186MaRDI QIDQ3557525zbMATH OpenFDO

Authors David Gamarnik, David A. Goldberg

Publication date 23 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548309990186

zbMATH Keywords

\(r\)-regular graphscardinality of independent setsweighted independent sets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• Experimental and Efficient Algorithms
• Local algorithms, regular graphs of large girth, and random regular graphs
• Large 2-independent sets of regular graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cites work

• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• An upper bound on the Ramsey numbers R(3,k)
• Computing independent sets in graphs with large girth
• Girth and Independence Ratio
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 1033855 (Why is no real title available?)
• Large independent sets in regular graphs of large girth
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• On Turan's theorem for sparse graphs
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Some simplified NP-complete graph problems
• The (2) limit in the random assignment problem

Cited in

(23)

• Analysis of greedy algorithms on graphs with bounded degrees
• Cooperation in partly observable networked markets
• On the instability of matching queues
• Local algorithms, regular graphs of large girth, and random regular graphs
• The matching process and independent process in random regular graphs and hypergraphs
• The jamming constant of uniform random graphs
• On the unified dispersion problem: efficient formulations and exact algorithms
• Markovian online matching algorithms on large bipartite random graphs
• Large 2-independent sets of regular graphs
• A greedy algorithm for finding a large 2‐matching on a random cubic graph
• The greedy independent set in a random graph with given degrees
• Independent dominating sets in graphs of girth five
• On the probe complexity of local computation algorithms
• Factor of iid percolation on trees
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Experimental and Efficient Algorithms
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• Borel fractional colorings of Schreier graphs
• Greedy maximal independent sets via local limits
• Asymptotic optimality of degree-greedy discovering of independent sets in configuration model graphs
• Combinatorics. Abstracts from the workshop held January 4--9, 2026
• Time lower bounds for the Metropolis process and simulated annealing
• A note on the greedy algorithm for finding independent sets of \(C_k\)-free graphs

This page was built for publication: Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections

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