Package com.jgalgo.alg.connect

Class MinimumVertexCutStEdgeCut

java.lang.Object

com.jgalgo.alg.connect.MinimumVertexCutStAbstract

com.jgalgo.alg.connect.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

Constructor Summary

Constructors

Constructor	Description
MinimumVertexCutStEdgeCut()	Create a new instance of the algorithm.

Method Summary

Methods inherited from class com.jgalgo.alg.connect.MinimumVertexCutStAbstract

computeMinimumCut

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MinimumVertexCutStEdgeCut

public MinimumVertexCutStEdgeCut()

Create a new instance of the algorithm.

Please prefer using MinimumVertexCutSt.newInstance() to get a default implementation for the MinimumVertexCutSt interface.