Finding most vital edges in a graph
Date
2007
Authors
Shen, H.
Editors
Gonzalez, T.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Book chapter
Citation
Handbook of Approximation Alggorithms and Metaheuristics, 2007 / Gonzalez, T. (ed./s), pp.62-1-62-16
Statement of Responsibility
Conference Name
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).