## 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 language | English |
---|---|

Title of host publication | Handbook of Approximation Algorithms and Metaheuristics |

Publisher | CRC Press |

Pages | 62-1-62-16 |

ISBN (Electronic) | 9781420010749 |

ISBN (Print) | 1584885505, 9781584885504 |

DOIs | |

Publication status | Published - 1 Jan 2007 |

Externally published | Yes |