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 (14)

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

This page was built for publication: Analysis of greedy algorithms on graphs with bounded degrees