On Survivable Set Connectivity

DOI10.1137/1.9781611973730.3zbMath1371.68205OpenAlexW4234874860MaRDI QIDQ5363080

Bundit Laekhanukit, Fabrizio Grandoni, Parinya Chalermsook

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.3

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40) Signed and weighted graphs (05C22)

Related Items

$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Unnamed Item ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs