Hardness of k-vertex-connected subgraph augmentation problem

DOI10.1007/S10878-008-9206-5zbMATH Open1206.90151OpenAlexW2143720330MaRDI QIDQ604752FDOQ604752

Authors Changcun Ma, Donghyun Kim, Yuexuan Wang, Wei Wang, Nassim Sohaee, Weili Wu

Publication date 12 November 2010

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-008-9206-5

zbMATH Keywords

network survivabilitygraph connectivity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• On the minimum local-vertex-connectivity augmentation in graphs
• scientific article; zbMATH DE number 2080985
• \(k\)-vertex-connectivity minimum augmentation for undirected unweighted graphs.
• On the cycle augmentation problem: hardness and approximation algorithms
• scientific article; zbMATH DE number 1617267

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Approximating theDomatic Number
• Approximation Algorithms for Several Graph Augmentation Problems
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• The hardness of approximation: Gap location

Cited in

(3)

• On robust clusters of minimum cardinality in networks
• On the cycle augmentation problem: hardness and approximation algorithms
• The VC-dimension of graphs with respect to \(k\)-connected subgraphs

This page was built for publication: Hardness of \(k\)-vertex-connected subgraph augmentation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q604752)