Algorithmic Graph Theory and its applications
<-- Return to the list
Date: 01-27-2009
Start Time:
5:00pm
End Time: 6:30pm
Speaker: Marty Golumbic, Haifa Univeristy
Location: Math 622
ABSTRACT
The topic about which I will be speaking, algorithmic graph theory, is part of the interface between combinatorial mathematics and computer science. I will begin by explaining and motivating the concept of an intersection graph, and I will provide examples of how they are useful for applications in computation, operations research, and even molecular biology.
The graph coloring problem on special families of these intersection graphs is of particular interest. We will see graph coloring algorithms being used for scheduling classrooms or airplanes, allocating machines or personnel to jobs, or designing circuits. Rich mathematical problems also arise in the study of intersection graphs, and a spectrum of research results, both simple and sophisticated, will be presented, which should interest both students and professors. At the end, I will provide a number of references for further reading.