Hardness of \(k\)-vertex-connected subgraph augmentation problem

DOI10.1007/s10878-008-9206-5zbMath1206.90151OpenAlexW2143720330MaRDI QIDQ604752

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

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

graph connectivitynetwork survivability

Mathematics Subject Classification ID

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

Related Items (1)

On robust clusters of minimum cardinality in networks

Cites Work

• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• The hardness of approximation: Gap location
• Approximation Algorithms for Several Graph Augmentation Problems
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximating theDomatic Number

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