Wagner Teixeira da Silva writes:
> Dear colleagues:
> Let G(V,E) is a non oriented graph; and A,B subset of V. I need find
> C, a minimal subset of V, that when removed causes A and B to be
> desconnected. I search for algorithms that find this kind of minimal
> cut set in non directed graph, so we will be grateful if anyone can
> suggest any references about it.
I suggest the following algorithm:
1. Collapse the vertices in A to a single vertex. Same for B.
2. Use one of the network flow algorithms to determine the connectivity
and find a cutset. See for example:
--- Frank Jensen, Frank.Jensen@hugin.com
Hugin Expert A/S Niels Jernes Vej 10 9220 Aalborg East DENMARK
This archive was generated by hypermail 2b29 : Thu Feb 28 2002 - 10:14:37 PST