Finding Most Vital Links over Time in a Flow Network

This paper deals with finding most vital links of a network which carries flows over time(also called ”dynamic flows”). Given a network and a time horizon T, Single Most Vital Link OverTime (SMVLOT) problem looks for a link whose removal results in greatest decrease in the value ofmaximum flow over time (dynamic maximum flow) up to time horizon T between two terminal nodes.SMVLOT problem is formulated as a mixed binary linear programming problem. This formulation isextended to a general case called k-Most Vital Links Over Time (KMVLOT) problem, in which we lookfor finding those k links whose removal makes greatest decrease in the value of maximum flow over time.A Benders decomposition algorithm is proposed for solving SMVLOT and KMVLOT problems. Forthe case of SMVLOT problem, the proposed algorithm is improved to a fully combinatorial algorithmby adopting an iterative method for solving existing integer programming problem. However, ourexperimental results showed the superiority of proposed methods.