| [home] - [up] |
Abstract: An interval graph is the intersection graph of a set of intervals on a line, and a circular-arc graph is the intersection graph of a set of arcs on a circle. Booth and Lueker discovered a linear-time algorithm for recognizing interval graphs in the mid 1970's, but at the time, Booth conjectured that the corresponding problem for circular-arc graphs would turn out to be NP complete. We have recently found a linear-time algorithm for the problem. Using a variety of techniques developed for that problem, we have developed a near-linear algorithm for recognizing probe-interval graphs, a linear algorithm for modular decomposition of directed graphs, O(|V|) algorithms for modular decomposition of interval graphs and permutation graphs when their well-known compact representations are given, and found a generalization of the so-called PQ tree to arbitrary 0-1 matrices, together with a linear-time algorithm to compute it. Using some of these results, we have developed algorithms to produce easily-checked certificates when a matrix does not have the consecutive-ones property, and when a graph is not an interval graph or a permutation graph. Such certificates are of practical importance when an implementation of an algorithm is distrusted.
Parts of the talk are based on joint work with Fabien de Montgolfier, Jerry Spinrad, Dieter Kratsch, Kurt Mehlhorn, and Wen-Lian Hsu.
Colloquium - 16:00
Abstract: Combinatorial optimization is often used to "plan ahead", purchasing and allocating resources for demands that are not precisely known at the time of solution. This advance planning may be done because resources become very expensive to purchase or difficult to allocate at the last minute when the demands are known. At other times, however, there is a possibility to "wait and see", deferring decisions about resource allocation until demands or constraints become clear. There is often a tradeoff involved, in that allocations made later may be more expensive. In this talk we will present a framework derived from stochastic programming for dealing with this time-information tradeoff in the presence of uncertainty.
We consider a number of combinatorial optimization problems (primarily in network design) in which the input is uncertain -modeled by a probability distribution- and in which elements can be purchased cheaply in advance or at greater expense after the distribution is sampled. We show how to approximately optimize the choice of what to purchase in advance and what to defer.