Approximating Rooted Steiner Networks
From MaRDI portal
Publication:4962166
DOI10.1145/2650183zbMath1398.68664OpenAlexW2141156487MaRDI QIDQ4962166
Bundit Laekhanukit, Guyslain Naves, Adrian Vetta, Joseph Cheriyan
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2650183
network designgraph connectivityapproximation algorithmshardness of approximationrooted connectivity
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)
Related Items (7)
$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 ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Steiner Problems with Limited Number of Branching Nodes
This page was built for publication: Approximating Rooted Steiner Networks
