On the optimal vertex-connectivity augmentation (Q1892828): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1995.1002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2048815229 / rank | |||
Normal rank |
Latest revision as of 22:37, 19 March 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