Approximating rooted Steiner networks

DOI10.1145/2650183MaRDI QIDQ4962166zbMATHOpenAlexFDO

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

zbMATH Keywords

approximation algorithmsnetwork designgraph connectivityhardness of approximationrooted connectivity

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)

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

Cited in

(10)

• 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
• Steiner problems with limited number of branching nodes
• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• Improved approximations for relative survivable network design
• Analysis of Steiner subtrees of random trees for traceroute algorithms
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)

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)