Department of Computer Science

9/12/1996

3:45pm-4:45pm

Connectivity is a central notion in graph theory. It indicates the difficulty of separating the vertices of a graph into disjoint pieces. For example, how sensitive is a communications network like the Internet to failures of links or sites?

This talk surveys the notion of graph connectivity. We define connectivity and illustrate how it relates to other basic properties of graphs. Then we survey algorithms that compute graph connectivity. The last five years have seen much progress in this area, involving several diverse techniques. We survey the recent algorithms for computing edge connectivity (i.e., link failures). These algorithms use techniques of graph searching, matroid algorithms and network flow algorithms. We also survey new algorithms for vertex connectivity (i.e., site failures). We concentrate on an algorithm recently discovered by the speaker and co-researchers, which combines previous ideas about vertex connectivity with one of the edge connectivity algorithms. Time permitting we conclude with speculation on the psychology of research: Why did it take 16 years to make this relatively simple advance in computing connectivity?

*Refreshments will be served immediately before the talk at 3:30pm.Hosted by Dirk Grunwald.*

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