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

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

zbMATH Keywords

network survivabilitygraph connectivity

Mathematics Subject Classification ID

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

Cites Work

• The hardness of approximation: Gap location
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Title not available (Why is that?)
• Approximating theDomatic Number
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximation Algorithms for Several Graph Augmentation Problems

Cited In (3)

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

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)