Advertisement
Published in:
2012 | OriginalPaper | Chapter
Degree-Constrained Node-Connectivity
Author : Zeev Nutov
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.