Analysis of greedy algorithms on graphs with bounded degrees

Research output: Contribution to journalArticleResearchpeer-review

27 Citations (Scopus)

Abstract

We give a general result on the average-case performance of certain greedy algorithms. These are derived from algorithms in which the possible operations performed at each step are prioritised. This type of prioritisation has occurred in previously studied heuristics for finding large subgraphs with special properties in random regular graphs, such as maximum independent sets and minimum dominating sets. The approach in this paper eliminates some of the complications caused by prioritisation. The main results apply in general to random graphs with a given degree sequence.

Original languageEnglish
Pages (from-to)235-260
Number of pages26
JournalDiscrete Mathematics
Volume273
Issue number1-3
DOIs
Publication statusPublished - 2003
Externally publishedYes

Keywords

  • Differential equations
  • Dominating set
  • Greedy algorithm
  • Independent set
  • Random graph
  • Regular graph

Cite this