A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design Problem

Details A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design Problem A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design Problem

2010-04-07

arxiv.org/abs/1004.1208v1

Computer Science

Data Structures and Algorithms

Scientific paper

In the vertex connectivity survivable network design problem we are given an undirected graph G = (V,E) and connectivity requirement r(u,v) for each pair of vertices u,v. We are also given a cost function on the set of edges. Our goal is to find the minimum cost subset of edges such that for every pair (u,v) of vertices we have r(u,v) vertex disjoint paths in the graph induced by the chosen edges. Recently, Chuzhoy and Khanna presented a randomized algorithm that achieves a factor of O(k^3 log n) for this problem where k is the maximum connectivity requirement. In this paper we derandomize their algorithm to get a deterministic O(k^3 log n) factor algorithm. Another problem of interest is the single source version of the problem, where there is a special vertex s and all non-zero connectivity requirements must involve s. We also give a deterministic O(k^2 log n) algorithm for this problem.

Affiliated with

Also associated with

No associations

Rating

A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design Problem 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 A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Deterministic Algorithm for the Vertex Connectivity Survivable Network Design Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-712844