An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees (Q1821118): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q274436 |
||
Property / reviewed by | |||
Property / reviewed by: Radim Jiroušek / rank | |||
Revision as of 05:56, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees |
scientific article |
Statements
An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees (English)
0 references
1987
0 references
Given a digraph G(V,E) the problem under study, called k-vertex- connectivity unweighted augmentation problem, is to find the smallest possible set E'\(\subset V\times V\) such that G'(V,E\(\cup E')\) is k- vertex-connected. The paper presents a survey of the known results concerning an algorithmical complexity of the problem for different types of graphs and different k. Then, the attention is focused on solving the problem for rooted directed trees. For this special case an algorithm is presented enabling to solve the problem in O(k\(| V|)\) time. Moreover, it is shown that the algorithm is optimal except for a constant factor.
0 references
rooted trees
0 references
k-vertex-connectivity
0 references
augmentation problem
0 references
rooted directed trees
0 references