Improved Algorithm for Degree Bounded Survivable Network Design Problem

We consider the Degree-Bounded Survivable Network Design Problem: the objective is to find a minimum cost subgraph satisfying the given connectivity requirements as well as the degree bounds on the vertices. If we denote the upper bound on the degree of a vertex v by b(v), then we present an algorit...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2009-11
Main Authors: Anand, Louis, Vishnoi, Nisheeth
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph theory
Minimum cost
Network design
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the Degree-Bounded Survivable Network Design Problem: the objective is to find a minimum cost subgraph satisfying the given connectivity requirements as well as the degree bounds on the vertices. If we denote the upper bound on the degree of a vertex v by b(v), then we present an algorithm that finds a solution whose cost is at most twice the cost of the optimal solution while the degree of a degree constrained vertex v is at most 2b(v) + 2. This improves upon the results of Lau and Singh and that of Lau, Naor, Salavatipour and Singh.
ISSN:2331-8422
DOI:10.48550/arxiv.0911.4544