Approximating rooted Steiner networks
DOI10.1145/2650183zbMATH Open1398.68664OpenAlexW2141156487MaRDI QIDQ4962166FDOQ4962166
Authors: B. 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
Recommendations
- scientific article; zbMATH DE number 7053371
- scientific article; zbMATH DE number 2119644
- 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
approximation algorithmsnetwork designgraph connectivityhardness 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)
Cited In (10)
- Steiner problems with limited number of branching nodes
- Analysis of Steiner subtrees of random trees for traceroute algorithms
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
- Improved approximations for relative survivable network design
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- Title not available (Why is that?)
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
This page was built for publication: Approximating rooted Steiner networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962166)
