Finding most vital edges in a graph

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

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

Original languageEnglish
Title of host publicationHandbook of Approximation Algorithms and Metaheuristics
PublisherCRC Press
Pages62-1-62-16
ISBN (Electronic)9781420010749
ISBN (Print)1584885505, 9781584885504
DOIs
Publication statusPublished - 1 Jan 2007
Externally publishedYes

Fingerprint

Dive into the research topics of 'Finding most vital edges in a graph'. Together they form a unique fingerprint.

Cite this