Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Degree-Constrained Node-Connectivity
verfasst von : Zeev Nutov
Erschienen in: LATIN 2012: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
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 give a general framework to handle
node-connectivity
degree constrained problems. In particular, for the
k
-Outconnected Subgraph
problem, for both directed and undirected graphs, our algorithm computes in polynomial time a solution
J
of cost
O
(log
k
) times the optimal, such that deg
J
(
v
) =
O
(2
k
) ·
b
(
v
) for all
v
∈
V
. Similar result are obtained for the
Element-Connectivity
and the
k
-Connected Subgraph
problems. The latter is a significant improvement on the particular case of only degree-approximation and undirected graphs considered in [5]. In addition, for the
edge-connectivity
directed
Degree-Constrained
k
-Outconnected Subgraph
problem, we slightly improve the best known approximation ratio, by a simple proof.