Iterative rounding approximation algorithms for degree-bounded node-connectivity network design

Details Iterative rounding approximation algorithms for degree-bounded node-connectivity network design Iterative rounding approximation algorithms for degree-bounded node-connectivity network design

2012-03-15

arxiv.org/abs/1203.3578v2

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b(\cdot) on nodes. We present an iterative rounding algorithm of the set-pair LP relaxation for this problem. When the graph is undirected and the connectivity requirements are on the element-connectivity with maximum value k, our algorithm computes a solution that is an O(k)-approximation for the edge cost in which the degree of each node v is at most O(k) \cdot b(v). We also consider the no edge cost case where the objective is to find a subgraph satisfying connectivity requirements and degree bounds. Our algorithm for this case outputs a solution in which the degree of each node v is at most 6b(v) + O(k^2). These algorithms can be extended to other well-studied undirected node-connectivity requirements such as spanning-, subset- and root-connectivity. When the graph is directed and the connectivity requirement is spanning k-out-connectivity from a root, our algorithm computes a solution that is a 2-approximation for the edge cost in which the degree of each node v is at most 2b(v) + O(k).

Affiliated with

Also associated with

No associations

Rating

Iterative rounding approximation algorithms for degree-bounded node-connectivity network design 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 Iterative rounding approximation algorithms for degree-bounded node-connectivity network design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterative rounding approximation algorithms for degree-bounded node-connectivity network design will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-348136