J. S. Provan

Department of Operations Research

University of North Carolina

Chapel Hill, NC 27599-3180

D. R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: This paper studies the generation of various types of (s,t)-cuts in directed and undirected graphs. We present a general paradigm for listing such (s,t)-cuts and we identify properties of classes of cuts that allow this approach to be applied. The paradigm lists the cuts in time linear in the number of cuts, with the time-per-cut complexity dependent upon that of a "pivot" subroutine applied at each step of the procedure. In addition to unifying known routines for enumerating minimal (s,t)-cuts in undirected graphs, uniformly directed (s,t)-cuts, and antichains in partial orders, the paradigm provides efficient generation schemes for several new classes of cuts: minimal (s,t)-cuts in directed graphs, minimum weight/cardinality (s,t)-cuts, "semi-directed" (s,t)-cuts, and classes of multi-terminal cuts. Except for the semi-directed cuts, all of the procedures have time-per-cut complexity that is linear in the size of the graph.

Key Words: algorithm, cut, enumeration, generation, ideal