Discrete Mathematics and Optimization Seminar


NICK WORMALD
University of Waterloo
Monday March 22th at 4.30pm
Burnside 1205



Title. Analysing Greedy Algorithms on Regular Graphs using Differential Equations.

Abstract. A regular graph is one with equal numbers of edges incident with each vertex. These graphs are
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.