Directed vertex-connectivity augmentation
type: Item
instance of: scholarly article
title: Directed vertex-connectivity augmentation
zbMATH Open document ID: 0934.05081
author: András Frank
author: Tibor Jordán
published in: Mathematical Programming. Series A. Series B
publication date: 2000-04-10T00:00:00Z
review text: The authors continue the study of the problem of finding a smallest set of new edges to be added to a given digraph to make it \(k\)-vertex-connected. First they prove some theoretical results about this problem, and then they give a combinatorial algorithm which solves this problem optimally in time \(O(k^6)\), for every fixed \(k\geq 1\).
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1332943
zbMATH Keywords: vertex-connectivity
zbMATH Keywords: digraph
zbMATH Keywords: combinatorial algorithm
reviewed by: Ferdinand Gliviak
MaRDI profile type: Publication
full work available at URL: s101070050038
OpenAlex ID: W2148988287
DOI: 10.1007/S101070050038
Recommended article: Primal-dual approach for directed vertex connectivity augmentation and generalizations
Recommended article: Q4472504
Recommended article: On the optimal vertex-connectivity augmentation
Recommended article: Q4370202
Recommended article: Connectivity augmentation of graphs
Recommended article: Hypergraph connectivity augmentation
Recommended article: Q4703856
Recommended article: Q3617662
Recommended article: Q2753943
description: scientific article; zbMATH DE number 1332943