Colloquium Details
Interval Graph Completion and Polynomial-Time Preprocessing
| Author: | Jan Arne Telle University of Bergen |
|---|---|
| Date: | October 18, 2007 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
This talk will start by arguing that the complexity class FPT can be used to capture the notion of polynomial-time preprocessing to reduce input size. This is followed by an FPT algorithm with runtime $O(n^{2k}n^{3}m)$ for the following NP-complete problem [GT35 in Garey&Johnson]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k edges to G? The given algorithm answers a question first posed by Kaplan, Shamir and Tarjan in 1994.
Biography
Jan Arne Telle is a professor at the University of Bergen and member of its algorithms research group. He earned his doctorate in computer science from the University of Oregon in 1994.