On the optimal vertex-connectivity augmentation (Q1892828): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q274436 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Radim Jiroušek / rank | |||
Normal rank |
Revision as of 05:56, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the optimal vertex-connectivity augmentation |
scientific article |
Statements
On the optimal vertex-connectivity augmentation (English)
0 references
2 July 1995
0 references
The optimal vertex-connectivity augmentation problem denotes the task of finding the minimum set of edges that should be added to a graph to increase its vertex-connectivity. The cardinality of such a minimal set for a graph \(G\) is denoted \(m(G)\). The author considers simple graphs and proves that for any \(k\)-connected graph \(G\) \((k\geq 2)\), \[ \max\{b(G)- 1, \lceil t(G)/2\rceil\}\leq m(G)\leq \max\{b(G)- 1, \lceil t(G)/2\rceil\} k- 2, \] where \(b(G)\) denotes the maximum number of components that can be achieved by removing \(k\) vertices from the graph \(G\), and \(t(G)\) equals the maximum number of pairwise disjoint minimal tight sets.
0 references
vertex-connectivity
0 references
polynomial-time algorithm
0 references
optimal vertex- connectivity augmentation
0 references
\(k\)-connected graph
0 references
tight sets
0 references