Analysis of greedy algorithms on graphs with bounded degrees

DOI10.1016/S0012-365X(03)00241-3zbMath1029.05147MaRDI QIDQ1417582

Nicholas C. Wormald

Publication date: 5 January 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Differential equationsGreedy algorithmDominating setIndependent setRandom graphRegular graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

The jamming constant of uniform random graphs, Bounds on the max and min bisection of random cubic and random 4-regular graphs, Decycling numbers of random regular graphs, Bounds on the bisection width for random \(d\)-regular graphs, Properties of regular graphs with large girth via local algorithms, A gentle introduction to the differential equation method and dynamic concentration, The cook-book approach to the differential equation method, Birth control for giants, Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm, THE DEPRIORITISED APPROACH TO PRIORITISED ALGORITHMS, Connected domination of regular graphs, Large independent sets in random regular graphs, Minimum 2-dominating sets in regular graphs, Minimum Power Dominating Sets of Random Cubic Graphs

Cites Work

• Maximum induced matchings of random cubic graphs
• Differential equations for random processes and random graphs
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• On the independence number of random cubic graphs
• Minimum independent dominating sets of random cubic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item