Date & Time: Thursday, 26th August 2010 at 10.30 a.m.
Venue: Ramanujan Hall
Title: "Algorithmic Graph Theory and its Applications: Twenty Five Years of EPT Graphs"
Speaker: Martin Charles Golumbic, Department of Computer Science, University of Haifa, Haifa, Israel
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, with 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.
We will then focus our attention to the family of edge intersection graphs of paths in a tree (the EPT graphs). Let $\cal{P}$ be a collection of nontrivial simple paths on a host tree $T$. The edge intersection graph of $\cal{P}$, denoted by $EPT(\cal{P})$, has vertex set that corresponds to the members of $\cal{P}$, where two vertices are joined by an edge if and only if the corresponding members of $\cal{P}$ share at least one common edge in $T$. An undirected graph $G$ is called an edge intersection graph of paths in a tree if $G$ = $EPT(\cal{P})$ for some $\cal{P}$ and $T$. The EPT graphs can be useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.
In this lecture, we will survey the mathematical and algorithmic results on EPT graphs and some of their generalizations. The class of EPT graphs was first investigated by Golumbic and Jamison in two papers appearing in 1985, and subsequently, further research has been carried out by a number of algorithmic graph theorists. On the algorithmic side, the recognition and coloring problems are NP-complete, whereas the maximum clique and maximum stable set problems are polynomially solvable. On the mathematical side, for example, it was shown in 1985 that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. Twenty years later in 2005, an analogous result by Golumbic, Lipshteyn and Stern showed that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4.
A complete hierarchy of related graph classes will also be presented, including the $k$-EPT graphs in which paths must share at least $k$ edges of the tree in order to generate an edge in the $k$-EPT graph. These, together with several restrictions on the tree representation, have been studied recently, and will be presented. We conclude with some open problems and future work.
About the Speaker:
Martin Charles Golumbic is Professor of Computer Science and Director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He is the founding editor-in-chief of the journal "Annals of Mathematics and Artificial Intelligence" (Springer), and is the author of the book "Algorithmic Graph Theory and Perfect Graphs" (Elsevier), and coauthor of the book "Tolerance Graphs" (Cambridge).
Professor Golumbic received his Ph.D. in mathematics from Columbia University in 1975. He has held positions at the Courant Institute of New York University, Bell Telephone Laboratories, IBM Research and Bar-Ilan University, and visiting positions at Universite de Paris, the Weizmann Institute of Science, and the Ecole Polytechnique de Lausanne. He is a Fellow of the Institute of Combinatorics and its Applications, and a Fellow of the European Artificial Intelligence society ECCAI.