On the optimal vertex-connectivity augmentation
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.
- Faster approximation algorithms for weighted triconnectivity augmentation problems
- Hypergraph connectivity augmentation
- Directed vertex-connectivity augmentation
- On the existence of (k,l)-critical graphs
- A note on the vertex-connectivity augmentation problem
- Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Independence free graphs and vertex connectivity augmentation
- Optimal augmentation of a 2-vertex-connected multigraph to an -edge-connected and 3-vertex-connected multigraph
- Approximating \(k\)-connected \(m\)-dominating sets
- Critical node detection problem for complex network in undirected weighted networks
- On the cycle augmentation problem: hardness and approximation algorithms
- Algorithm and complexity of the two disjoint connected dominating sets problem on trees
- Approximating subset \(k\)-connectivity problems
- Property testing on \(k\)-vertex-connectivity of graphs
- Approximating node-connectivity augmentation problems
- Globally rigid augmentation of minimally rigid graphs in \(\mathbb{R}^2\)
- Multigraph augmentation under biconnectivity and general edge-connectivity requirements
- Extension to Even Triangulations
- Approximating minimum-cost edge-covers of crossing biset-families
- An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
- Extremal graphs in connectivity augmentation
- scientific article; zbMATH DE number 2080985 (Why is no real title available?)
- Structured connectivity augmentation
- Augmenting edge-connectivity between vertex subsets
- Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
- Primal-dual approach for directed vertex connectivity augmentation and generalizations
- Globally rigid augmentation of rigid graphs
- How to make a strongly connected digraph two-connected
- Structured connectivity augmentation
- Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
- Improved approximation algorithms for min-cost connectivity augmentation problems
- Approximating k-Connected m-Dominating Sets
- Augmenting trees so that every three vertices lie on a cycle
- Node connectivity augmentation via iterative randomized rounding
- An approximation algorithm for minimum-cost vertex-connectivity problems
- Graph connectivity and its augmentation: Applications of MA orderings
- The structure of minimum vertex cuts
- The price of connectivity augmentation on planar graphs
- On shredders and vertex connectivity augmentation
This page was built for publication: On the optimal vertex-connectivity augmentation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892828)
