Matching Based Augmentations for Approximating Connectivity Problems

DOI10.1007/11682462_4MaRDI QIDQ3525741zbMATH OpenOpenAlexFDO

Authors R. Ravi

Publication date 18 September 2008

Published in LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11682462_4

Mathematics Subject Classification ID

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

Recommendations

• A simple LP-based approximation algorithm for the matching augmentation problem
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• scientific article; zbMATH DE number 742977
• LP-relaxations for tree augmentation
• A General Approximation Technique for Constrained Forest Problems

Cited in

(10)

• New approaches to multi-objective optimization
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• An improvement on Łuczak's connected matchings method
• An improved approximation algorithm for the matching augmentation problem
• A simple LP-based approximation algorithm for the matching augmentation problem
• The Steiner path aggregation problem
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• Approximating connectivity augmentation problems
• Approximating minimum-cost connected \(T\)-joins

This page was built for publication: Matching Based Augmentations for Approximating Connectivity Problems

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