Approximating spanners and directed Steiner forest. Upper and lower bounds

DOI10.1145/3381451MaRDI QIDQ4987451zbMATH OpenOpenAlexFDO

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 algorithmsdirected spannerdirected Steiner foresthardness of approximationnetwork design

Mathematics Subject Classification ID

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

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

(9)

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

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)