Combinatorial Optimization and Recognition of Graph Classes with Applications to Related Models

Speaker

Dipl.-Math. George B. Mertzios , Chair of Computer Science 1
Title Combinatorial Optimization and Recognition of Graph Classes with Applications to Related Models
When 30. 11. 2009, 14.00
Where Seminarraum 4017
Abstract Interval structures arise naturally in many applications, as in genetics, molecular biology, and scheduling, among others. Such structures are often modeled with graphs. In this talk we mainly investigate some widely studied classes of graphs that can be represented using interval structures, as well as a scheduling problem. We present solutions to some open problems, along with some new representation models that enable the design of new efficient algorithms.

In particular, we first investigate the class of interval graphs. We present the first polynomial algorithm for the longest path problem on this class, whose complexity status was an open question. Furthermore, we introduce two matrix representations for both interval and proper interval graphs, which enable the design of a polynomial algorithm for the k-fixed-endpoint path cover problem on proper interval graphs with optimal running time.

Next, we investigate tolerance graphs. We present the first non-trivial intersection model for this class, given by three-dimensional parallelepipeds, which enables the design of efficient algorithms for problems, such as coloring and clique. Furthermore, we prove that both recognition problems for tolerance and bounded tolerance graphs are NP-complete, thereby settling a long standing open question since 1982.