Approximating spanners and directed Steiner forest. Upper and lower bounds

DOI10.1145/3381451MaRDI QIDQ4987451zbMATHOpenAlexFDO

Authors Eden Chlamtac, Michael Dinitz, B. Laekhanukit, Guy Kortsarz

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsnetwork designhardness of approximationdirected Steiner forestdirected spanner

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distance in graphs (05C12)

Recommendations

• Approximating spanners and directed Steiner forest: upper and lower bounds
• Approximation algorithms for spanner problems and directed Steiner forest
• Improved approximation for the directed spanner problem
• scientific article; zbMATH DE number 2079365
• scientific article; zbMATH DE number 1182768

Cited in

(6)

• Approximation algorithms for spanner problems and directed Steiner forest
• Reachability preservers: new extremal bounds and approximation algorithms
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Online Directed Spanners and Steiner Forests.
• An ETH-tight algorithm for bidirected Steiner connectivity
• scientific article; zbMATH DE number 2079365 (Why is no real title available?)

This page was built for publication: Approximating spanners and directed Steiner forest. Upper and lower bounds

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