2014 | OriginalPaper | Buchkapitel
A Unified Algorithm for Degree Bounded Survivable Network Design
verfasst von : Lap Chi Lau, Hong Zhou
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present an approximation algorithm for the minimum bounded degree Steiner network problem that returns a Steiner network of cost at most two times the optimal and the degree on each vertex
v
is at most min {
b
v
+ 3
r
max
, 2
b
v
+ 2}, where
r
max
is the maximum connectivity requirement and
b
v
is the given degree bound on
v
. This unifies, simplifies, and improves the previous results for this problem.