Monday March 22th at 4.30pm

a commonly studied class of graphs. A number of results have been obtained recently which analyse greedy algorithms

on regular graphs, and how they perform on average. I will discuss the current use of the differential equation

method for this purpose. Some of the examples considered include the greedy construction of small dominating sets,

large induced matchings and large 2-independent sets in regular graphs. The primary aim of these algorithms has been

to obtain bounds on the sizes of these sets in almost all regular graphs. Some of the results obtained recently give

new upper bounds on the minimum bisection width of random regular graphs, which is of interest in theoretical

computer science.