Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections

DOI10.1017/S0963548309990186zbMath1213.90252MaRDI QIDQ3557525

David A. Goldberg, David Gamarnik

Publication date: 23 April 2010

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (11)

The jamming constant of uniform random graphs ⋮ On the unified dispersion problem: efficient formulations and exact algorithms ⋮ Factor of IID Percolation on Trees ⋮ Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth ⋮ Cooperation in partly observable networked markets ⋮ Markovian online matching algorithms on large bipartite random graphs ⋮ Borel fractional colorings of Schreier graphs ⋮ Unnamed Item ⋮ On the instability of matching queues ⋮ Independent dominating sets in graphs of girth five ⋮ The matching process and independent process in random regular graphs and hypergraphs

Cites Work

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

This page was built for publication: Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections