Computer Science – Data Structures and Algorithms
Scientific paper
2009-08-03
Computer Science
Data Structures and Algorithms
Scientific paper
We study a number of multi-route cut problems: given a graph G=(V,E) and connectivity thresholds k_(u,v) on pairs of nodes, the goal is to find a minimum cost set of edges or vertices the removal of which reduces the connectivity between every pair (u,v) to strictly below its given threshold. These problems arise in the context of reliability in communication networks; They are natural generalizations of traditional minimum cut problems where the thresholds are either 1 (we want to completely separate the pair) or infinity (we don't care about the connectivity for the pair). We provide the first non-trivial approximations to a number of variants of the problem including for both node-disjoint and edge-disjoint connectivity thresholds. A main contribution of our work is an extension of the region growing technique for approximating minimum multicuts to the multi-route setting. When the connectivity thresholds are either 2 or infinity (the "2-route cut" case), we obtain polylogarithmic approximations while satisfying the thresholds exactly. For arbitrary connectivity thresholds this approach leads to bicriteria approximations where we approximately satisfy the thresholds and approximately minimize the cost. We present a number of different algorithms achieving different cost-connectivity tradeoffs.
Barman Siddharth
Chawla Shuchi
No associations
LandOfFree
Region growing for multi-route cuts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Region growing for multi-route cuts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Region growing for multi-route cuts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-556394