On the optimal vertex-connectivity augmentation

DOI10.1006/JCTB.1995.1002zbMATH Open0824.05042OpenAlexW2048815229MaRDI QIDQ1892828FDOQ1892828

Publication date: 2 July 1995

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.1995.1002

Recommendations

scientific article; zbMATH DE number 1617267
\(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs.
Extremal graphs in connectivity augmentation
Connectivity augmentation of graphs

tight sets polynomial-time algorithm vertex-connectivity \(k\)-connected graph optimal vertex- connectivity augmentation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Connectivity (05C40)

Cited In (38)

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