An improved approximation algorithm for the matching augmentation problem

DOI10.4230/LIPICS.ISAAC.2021.38MaRDI QIDQ6147541zbMATH OpenFDO

Authors Joseph Cheriyan, Robert Cummings, Jack Dippel

Publication date 15 January 2024

zbMATH Keywords

approximation algorithmsnetwork designconnectivity augmentationmatching augmentation problem2-edge connected graph2-edge coversforest augmentation problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• An Improved Approximation Algorithm for the Matching Augmentation Problem
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• A simple LP-based approximation algorithm for the matching augmentation problem
• Approximation Algorithms for Graph Augmentation
• Matching Based Augmentations for Approximating Connectivity Problems

This page was built for publication: An improved approximation algorithm for the matching augmentation problem

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