On the maximum size of a minimal k-edge connected augmentation

DOI10.1016/J.JCTB.2011.06.004zbMATH Open1235.90172OpenAlexW2061275745MaRDI QIDQ765200FDOQ765200

Authors: Andreĭ V. Kotlov, Joseph Cheriyan 

Publication date: 19 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.jctb.2011.06.004

Recommendations

• Edge-connectivity augmentation problems
• Edge-Connectivity Augmentation Preserving Simplicity
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• The minimum augmentation of any graph to aK-edge-connected graph
• scientific article; zbMATH DE number 1617267

zbMATH Keywords

approximation algorithmsedge connectivityconnectivity augmentation\(k\)-edge connected spanning subgraphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25) Connectivity (05C40)

Cites Work

• Graph theory
• Approximation algorithms for NP-hard problems.
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Biconnectivity approximations and graph carvings
• Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen
• Title not available (Why is that?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity

Cited In (3)

• Can we create large \(k\)-cores by adding few edges?
• Minimum augmentation of a tree to a K-edge-connected graph
• The minimum augmentation of any graph to aK-edge-connected graph

This page was built for publication: On the maximum size of a minimal \(k\)-edge connected augmentation

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