Finding most vital edges in a graph

Hong Shen

研究成果: Chapter同行評審

摘要

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).

原文English
主出版物標題Handbook of Approximation Algorithms and Metaheuristics
發行者CRC Press
頁面62-1-62-16
ISBN(電子)9781420010749
ISBN(列印)1584885505, 9781584885504
DOIs
出版狀態Published - 1 1月 2007
對外發佈

指紋

深入研究「Finding most vital edges in a graph」主題。共同形成了獨特的指紋。

引用此