Edge-connectivity augmentation problems
type: Item
instance of: scholarly article
title: Edge-connectivity augmentation problems
zbMATH Open document ID: 0622.68057
DOI: 10.1016/0022-0000(87)90038-9
author: B. George
published in: Journal of Computer and System Sciences
publication date: 1987-01-01T00:00:00Z
review text: We give a characterization on the minimum number of edges to be added so as to k-edge-connect a graph. We also show that such a minimum edge set can be determined in \({\mathcal O}(kL| V|^ 4(k| V| +| E|))\) time for any graph \(G=(V,E)\) and any fixed \(k\geq 2\), where \(L=\min \{k,| V| \}\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4009833
zbMATH Keywords: minimum edge set
MaRDI profile type: Publication
full work available at URL: 0022-0000(87)90038-9
OpenAlex ID: W2067818080
cites work: Q4091421
cites work: Q3852212
cites work: Augmentation Problems
cites work: Q3883524
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: `` Strong '' NP-Completeness Results
cites work: Parallel concepts in graph theory
cites work: Q5595961
cites work: Q5585021
cites work: A Reduction Method for Edge-Connectivity in Graphs
cites work: Smallest Augmentations to Biconnect a Graph
description: scientific article; zbMATH DE number 4009833