The Science Seminar Series: Febrauary 11, 2010
Distributed Bipartite Matching and Its Applications to Network Switch Scheduling
Dr. Krishnendu Roy
Math and Computer Science
Valdosta State University
Time: 4:00 -5:00pm
Graph theory is an important branch of Computer Science that deals with modeling various real life discrete problems. Graph matching is an important problem of graph theory. Selecting a subset of edges of a graph such that no two edges have the same end-points is known as graph matching. When a matching is computed on a special kind of graph, bipartite graph, the problem is called bipartite graph matching or simply bipartite matching. Bipartite matching is relatively easy to understand, yet one can use it to solve various complicated problems spanning different scientific disciplines including computer science, operations research, and bioinformatics. Part of my research involves using a mesh like structure of processing elements to generate bipartite matching in a distributed fashion. Generating matching is a computationally intensive task; hence distributed approaches are often preferred. In this talk I will give an overview of general graph matching, bipartite matching, and some applications of bipartite matching. Subsequently, I will present a distributed bipartite matching algorithm that we developed as a part of my doctoral research. Our algorithm runs on a distributed 2-D mesh of processing elements and is very efficient. The mesh layout of processing elements is very similar in structure to a network switch and hence is well suited for that application.