Approximating spanners and directed Steiner forest. Upper and lower bounds

DOI10.1145/3381451zbMATH Open1484.68156OpenAlexW3035713054MaRDI QIDQ4987451FDOQ4987451

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

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

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)

Cited In (6)

• An ETH-tight algorithm for bidirected Steiner connectivity
• Title not available (Why is that?)
• Reachability preservers: new extremal bounds and approximation algorithms
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Online Directed Spanners and Steiner Forests.
• Approximation algorithms for spanner problems and directed Steiner forest

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)