Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Pebble games for graph arboricity
Speaker: Ileana Streinu, Smith College & U. Mass Amherst
Date: March 31, 2005 4:30-5:30pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The pebble game algorithm, invented by Hendrickson and Jacobs for the study of 2-dimensional generically rigid graphs, is an elegant and efficient paradigm underlying modern research on protein flexibility. We analyze extensions of the original algorithm to a family of pebble games induced by two parameters k and l. They characterize graphs which can be turned into edge-disjoint unions of k spanning trees via the addition of **ANY** l edges, and which satisfy hereditarily a linear inequality of the form m <= k(n-1) - l between the number of vertices and edges. They have well known matroidal properties for values of l in the interval [0,k) but not otherwise. In this setting, the "maximal components" are indicators of critical subgraphs for a variety of tasks, and correspond to rigid components in the protein flexibility applications. We show how to compute them efficiently and how to use them to obtain new algorithms for Henneberg sequences and edge-disjoint tree partitionings. As a side-effect we improve some other existing algorithms involving pseudo-triangulations. Along the way, the well known theorem of Tutte and Nash-Williams on edge-disjoint tree decompositions will be extended with a characterization via pebble games. I will use a variety of graphical props to illustrate the algorithms (presented indeed as "games") and some of their applications.
This is joint work with Audrey Lee and Louis Theran from University of Massachusetts at Amherst.