Finding the k Most Vital Elements of an s-t Planar Directed Network


Dimiter Ivanchev




For a given s-t planar directed network with lower and upper arc capacities we find those k arcs the removal of which minimizes the flow value of the maximum flow. Such arcs are called the k most vital arcs of the network. Analogously we find the k most vital nodes. Further more, we find the k bicriterial lexicographical most vital elements, the removal of which minimizes the maximum flow value first, and on the other hand, is the "cheapest" variant. Such problems arise if one wants to know in advance what the consequences will be if some of the network elements terminate their function or have to be switched off.