
Speaker: Michael Kielstra
Title: The Fisherman, the Graduate, and the Robot: Linear Programming for Applied Graph Theory
Abstract: Graphs, which are collections of vertices and edges joining them,
give us visual representations of networks. A perfect matching is a set of
edges of a graph such that every vertex is covered by exactly one edge in
the matching. These types of matchings can be used to find ways to allocate
resources or assign tasks to large networks of people or organizations.
Methods of finding perfect matchings have been put forward and refined
since Jack Edmonds found the first one in 1958. In this talk we will
discuss Edmond's algorithm for finding perfect matchings as well as
recent improvements on it.
