Firefighter problem - finding min-cut in capacitated network (Help)

36 Views Asked by At

As my final project my colleagues and I chose to research the firefighter problem. We could really use your help in the section of MIN-BUDGET regarding the DirlayNet (Directed layered network) Approach.

From my understanding, a capitated network is a flow network just that instead of its edges having a capacity now its nodes have a capacity (as we calculated in the first step of the algorithm).

we could use a hint/explanation/article on how to find a Min S-T Cut in a capacitated network.

The algorithm is as follows: H(l) - approx. - (DIRLAY)

1. Set capacity of each vertex v∈L_i at 1/((i*H(l))). (l = number of layers)
2. Find the min S-T cut in this capacitated network // (this is where we need help) //
    Denote it as - (N_1 ...  N_l ),N_i⊆ L_i.
3.The algorithm vaccinates the vertices of N_j as follows: 
      Construct an upper triangular matrix - M’.
      M'ij: = |N_j|/j ,1≤i≤j≤l. (For any column j, the col sum is exactly|N_j|)
4.Construct an integral matrix M from M’ (by using a network graph to upper/lower the values of M’).
5.Vaccination strategy - On time step i, vaccinate M_ij nodes from layer j, 1≤i≤l.

Thanks for your time :)