The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
From MaRDI portal
Publication:2191772
DOI10.1007/s10107-019-01394-zzbMath1452.90309arXiv1810.07816MaRDI QIDQ2191772
Joseph Cheriyan, Fabrizio Grandoni, Arindam Khan, Vishnu V. Narayan, J. Dippel
Publication date: 26 June 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.07816
network design; approximation algorithms; bridges; connectivity augmentation; matching augmentation problem; 2-edge connected graph; 2-edge covers; forest augmentation problem
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms