An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
type: Item
instance of: scholarly article
title: An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
zbMATH Open document ID: 0616.05045
DOI: 10.1016/0166-218X(87)90007-2
author: Toshimitsu Masuzawa
author: Ken'ichi Hagihara
author: Nobuki Tokura
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 3997839
zbMATH Keywords: rooted trees
zbMATH Keywords: k-vertex-connectivity
zbMATH Keywords: augmentation problem
zbMATH Keywords: rooted directed trees
reviewed by: Radim Jiroušek
MaRDI profile type: Publication
cites work: Q4065051
cites work: Q3852212
cites work: Augmentation Problems
cites work: Q3883524
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: Q4198056
full work available at URL: 0166-218x(87)90007-2
OpenAlex ID: W1991573073
description: scientific article; zbMATH DE number 3997839