A Linear Time Algorithm for Computing Max-Flow Vitality in Undirected Unweighted Planar Graphs

Giorgio Ausiello, Lorenzo Balzotti, Paolo G. Franciosa +2

The vitality of an edge in a graph with respect to the maximum flow between two fixed vertices $s$ and $t$ is defined as the reduction of the maximum flow value caused by the remov…