Department of Computer Science

2/1/1996

3:45pm-5:00pm

The splitting operation for graphs is a simple yet powerful device. It is useful for proving theorems on graphs and designing efficient algorithms. Splitting was developed starting in the 1970's in Europe; it has recently begun to attract more attention. This talk surveys several representative applications of splitting: graph orientation, packing arborescences and multicommodity flow. We discuss theorems proved by splitting, and efficient algorithms based on the proofs.

One of our splitting algorithms involves a computation that can be done using
*n* binary searches. We show how to reduce this to 1 binary search.
We'll explain the method in detail, since it's quite simple. Surprisingly
this binary search algorithm does not seem to have been previously known.

*Refreshments will be served immediately before the talk at 3:30pm.*

Department of Computer Science

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu

University of Colorado Boulder

Boulder, CO 80309-0430 USA

webmaster@cs.colorado.edu