Package com.jgalgo.alg.connect

Class MinimumVertexCutStEdgeCut

  • All Implemented Interfaces:
    MinimumVertexCutSt
    public class MinimumVertexCutStEdgeCut
extends MinimumVertexCutStAbstract
    Minimum Vertex-Cut algorithm with terminal vertices (source-sink, S-T) using Minimum Edge-Cut algorithm.

    An auxiliary graph is constructed from the original graph \(G=(V,E)\) by replacing each vertex \(v\) with two vertices \(v_0\) and \(v_1\) connected with an edge \((v_0,v_1)\), and each edge \(e=(u,v)\) with an edge with either one or two edges. If the original graph is directed, then the edge \((u,v)\) is replaced with the edge \((u_1,v_0)\). If the original graph is undirected, then the edge \((u,v)\) is replaced with the edges \((u_1,v_0)\) and \((v_1,u_0)\). The edges connecting the vertices \(v_0\) and \(v_1\) are weighted with the weight of the vertex \(v\) in the original graph. The edges connecting the vertices \(u_1\) and \(v_0\) are weighted with a large enough weight such that the minimum edge-cut in the auxiliary graph will not contain any of these edges. The minimum edge-cut in the auxiliary graph is computed using the MinimumEdgeCutSt algorithm. The minimum vertex-cut in the original graph is the set of vertices corresponding to the edges in the minimum edge-cut in the auxiliary graph.

    Author:
    Barak Ugav