ISSN:
1432-0541
Keywords:
Algorithm
;
Cut
;
Enumeration
;
Generation
;
Ideal
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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, “semidirected” (s, t)-cuts, and classes of multiterminal cuts. Except for the semidirected cuts, all of the procedures have time-per-cut complexity that is linear in the size of the graph.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01961544
Permalink
