[UAI] (A,B|C) - find a minimal C that desconnect A and B in G(V,E).

From: Frank Jensen (Frank.Jensen@hugin.com)
Date: Thu Feb 28 2002 - 10:12:41 PST

  • Next message: Petros Groumpos: "[UAI] The 4th International Workshop on Computer Science and Information Technologies"

    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,   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