On survivable set connectivity

DOI10.1137/1.9781611973730.3MaRDI QIDQ5363080zbMATH OpenOpenAlexFDO

Authors Parinya Chalermsook, Fabrizio Grandoni, B. Laekhanukit

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

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

Recommendations

• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Inapproximability of Survivable Networks
• Inapproximability of survivable networks

Cited in

(6)

• Survivable network design for group connectivity in low-treewidth graphs
• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
• From directed Steiner tree to directed polymatroid Steiner tree in planar graphs
• Survivable network design with group-to-group requirement

This page was built for publication: On survivable set connectivity

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