Colloquium Details
Making arbitrary graphs transitively orientable: minimal comparability completions
| Author: | Pinar Heggernes University of Bergen, Norway |
|---|---|
| Date: | November 09, 2006 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes $\Pi$ for which $\Pi$ completion of arbitrary graphs can be achieved through such a vertex incremental approach. This is a joint work with Federico Mancini and Charis Papadopoulos.
Biography
Pinar Heggernes is a professor at the Department of Informatics, University of Bergen, Norway. Her main research interests are in graph algorithms in general, and algorithms related to special graph classes and various graph decomposition models in particular. Her web page http://www.ii.uib.no/~pinar gives more detailed information about her research, publications, and students.
Pinar is planning to spend the academic year 2007-2008 at the University of Oregon as a visiting professor.