Math table October 2, 2019
|
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. |
