Approximation algorithms for directed weighted spanners

DOI10.1007/S00453-026-01384-6MaRDI QIDQ7239686zbMATH OpenFDO

Authors Elena Grigorescu, Nithish Kumar, Young-San Lin

Publication date 8 May 2026

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-026-01384-6

zbMATH Keywords

approximation algorithmsdirected spannersdirected Steiner forestsonline algorithms

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• A general approach to online network optimization problems
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A simple efficient approximation scheme for the restricted shortest path problem
• All-Pairs Almost Shortest Paths
• An improved approximation scheme for the Group Steiner Problem
• An Optimal Synchronizer for the Hypercube
• Approximate distance oracles with improved bounds
• Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• Approximating directed buy-at-bulk network design
• Approximating low-stretch spanners
• Approximating spanners and directed Steiner forest. Upper and lower bounds
• Approximating the Minimum Equivalent Digraph
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for spanner problems and directed Steiner forest
• Approximation Schemes for the Restricted Shortest Path Problem
• Automata, Languages and Programming
• Bicriteria network design problems
• Compact roundtrip routing in directed networks
• Computing almost shortest paths
• Directed spanners via flow-based linear programs
• Distance oracles beyond the Thorup-Zwick bound
• Euclidean prize-collecting Steiner forest
• Faster algorithms for all-pairs approximate shortest paths in undirected graphs
• Fault-tolerant spanners
• Graph spanners
• Graph spanners: a tutorial review
• Having hope in hops: new spanners, preservers and lower bounds for hopsets
• Hop-constrained metric embeddings and their applications
• Improved approximation algorithms for directed Steiner forest
• Multi-criteria approximation schemes for the resource constrained shortest path problem
• New results on linear size distance preservers
• On the hardness of approximating spanners
• Online Buy-at-Bulk Network Design
• Online Directed Spanners and Steiner Forests.
• Optimal Efficiency Guarantees for Network Design Mechanisms
• Parameterized complexity of directed spanner problems
• Reachability preservers: new extremal bounds and approximation algorithms
• Roundtrip spanners and roundtrip routing in directed graphs
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
• Testing Lipschitz functions on hypergrid domains
• The hardness of approximating spanner problems
• Transitive-closure spanners
• Tree embeddings for hop-constrained network design

This page was built for publication: Approximation algorithms for directed weighted spanners

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