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

DOI10.1016/J.JCTB.2011.06.004MaRDI QIDQ765200zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

\(k\)-edge connected spanning subgraphsapproximation algorithmsconnectivity augmentationedge connectivity

Mathematics Subject Classification ID

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

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

Cites work

• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximation algorithms for NP-hard problems.
• Biconnectivity approximations and graph carvings
• Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen
• Graph theory
• scientific article; zbMATH DE number 5764784 (Why is no real title available?)
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 2079404 (Why is no real title available?)

Cited in

(5)

• 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
• Edge-Connectivity Augmentation Preserving Simplicity
• Edge-connectivity augmentation of simple graphs

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)