[Fall 1998
Colloquiums]
[Department Homepage]
DEPARTMENT OF MATHEMATICS AND STATISTICS
OAKLAND UNIVERSITY
ROCHESTER, MICHIGAN 48309
Eddie Cheng
Department of Mathematics and Statistics
Oakland University
Submodular Functions, Polymatroids and Strength
Abstract
Vulnerability issues are important aspects in network analysis. The most
basic measures (and often too simplistic) are connectivity and edge-connectivity,
which are well-studied; many efficient algorithms are available to compute
these values for a given network. Other more advanced measures include toughness
(Chvátal), integrity and edge-integrity (Barefoot et. al.). These
measures are NP-hard and hence, most likely, too difficult to compute
in general. Strength (Gusfield, 1983) is an edge version of toughness that
was motivated by a theorem of Tutte and is computable in polynomial time.
The original algorithm involves matroid partition. Subsequent improvements
include Cunningham (1985), Gusfield (1991), Barahona (1992), and Cheng and
Cunningham (1994). All of them use a version of Edmonds' theorem on polymatroids,
and two of them utilize an advanced network flow algorithm of Gallo, Grigoriadis
and Tarjan. Although such efficient algorithms exist, certain interconnection
networks have exponentially large numbers of vertices, so it is desirable
to compute the strength quickly for these networks. These networks are regular
graphs. In this talk, we give a general algorithm for computing the strength
of a network (joint work with Cunningham) and give a formula for the weighted
version of the strength of an r regular graph (joint work with Lipman).
372 Science and Engineering Building
Tuesday, November 17, 1998
3:004:00 P.M.
Refreshments at 2:303:00 P.M. in Room 368, Science and Engineering Building