TY - CHAP

T1 - Finding most vital edges in a graph

AU - Shen, Hong

N1 - Publisher Copyright:
© 2007 by Taylor & Francis Group, LLC.

PY - 2007/1/1

Y1 - 2007/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85056068803&partnerID=8YFLogxK

U2 - 10.1201/9781420010749

DO - 10.1201/9781420010749

M3 - Chapter

AN - SCOPUS:85056068803

SN - 1584885505

SN - 9781584885504

SP - 62-1-62-16

BT - Handbook of Approximation Algorithms and Metaheuristics

PB - CRC Press

ER -