Approximation Algorithms for Several Graph Augmentation Problems
From MaRDI portal
Publication:3910552
DOI10.1137/0210019zbMath0461.05040MaRDI QIDQ3910552
Greg N. Frederickson, Joseph F. Ja'Ja'
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210019
augmentation; approximation algorithm; strong connectivity; NP-complete problem; bridge-connectivity
05C35: Extremal problems in graph theory
60C05: Combinatorial probability
05C40: Connectivity
68W99: Algorithms in computer science
Related Items
A minimum 3-connectivity augmentation of a graph, Faster approximation algorithms for weighted triconnectivity augmentation problems, An efficient approximation algorithm for the survivable network design problem, A smallest augmentation to 3-connect a graph, A primal-dual approximation algorithm for generalized Steiner network problems