ABSTRACT
In many applications such as design of transportation networks, we often need to identify a set of regions/sections whose damage will cause the greatest increase in transportation cost within the network so that we can set extra protection to prevent them from being damaged. Modeling a transportation network with a weighted graph, a set of regions with a set of edges in the graph, transportation cost within the network with a particular property of the graph, we can convert this real-application problem to the following graph-theoretic problem: finding a set of edges in the graph, namely most vital edges or MVE for short, whose removal will cause the greatest damage to a particular property of the graph. The problems are traditionally referred to as prior analysis problems in sensitivity analysis (see Chapter 30).
