Analysis of greedy algorithms on graphs with bounded degrees Original Research Article

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.