Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

DOI10.1145/3055399.3055445zbMath1370.68231OpenAlexW2626235428MaRDI QIDQ4977990

Fabrizio Grandoni, Bundit Laekhanukit

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3055399.3055445

zbMATH Keywords

approximation algorithmsgroup Steiner treesurvivable network designdirected Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

This page was built for publication: Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree