Approximating Spanners and Directed Steiner Forest

DOI10.1145/3381451zbMath1484.68156OpenAlexW3035713054MaRDI QIDQ4987451

Eden Chlamtáč, Bundit Laekhanukit, Michael Dinitz, 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

network designapproximation algorithmshardness of approximationdirected Steiner forestdirected spanner

Mathematics Subject Classification ID

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

Related Items (1)

An ETH-tight algorithm for bidirected Steiner connectivity

This page was built for publication: Approximating Spanners and Directed Steiner Forest