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: http://www.cs.sunysb.edu/~algorith/files/edge-vertex-connectivity.shtml Best regards --- Frank Jensen, [EMAIL PROTECTED] Hugin Expert A/S Niels Jernes Vej 10 9220 Aalborg East DENMARK
