skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · colloquia · 1996-1997 · 

Colloquium - Gabow

ECCR 265

A Survey of Graph Connectivity: Applications & How to Compute It
Department of Computer Science
Harold (Hal) Gabow photo

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.

The Department holds colloquia throughout the Fall and Spring semesters. These colloquia, open to the public, are typically held on Thursday afternoons, but sometimes occur at other times as well. If you would like to receive email notification of upcoming colloquia, subscribe to our Colloquia Mailing List. If you would like to schedule a colloquium, see Colloquium Scheduling.

Sign language interpreters are available upon request. Please contact Stephanie Morris at least five days prior to the colloquium.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:29)