Bounded-degree light approximate shortest-path trees in doubling metrics
From MaRDI portal
Publication:2235274
DOI10.1016/j.dam.2021.08.039zbMath1479.90206OpenAlexW3202520833MaRDI QIDQ2235274
Julián Mestre, Seeun William Umboh, Joachim Gudmundsson
Publication date: 21 October 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2021.08.039
Cites Work
- A note on two problems in connexion with graphs
- On the shortest spanning subtree of a graph and the traveling salesman problem
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
- Approximation algorithms for the shortest total path length spanning tree problem
- Balancing minimum spanning trees and shortest-path trees
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- Optimum Communication Spanning Trees
- Additive Guarantees for Degree-Bounded Directed Network Design
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- Worst-Case Analysis of Network Design Problem Heuristics
- The complexity of the network design problem
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Spanning Trees and Optimization Problems
- Light graphs with small routing cost
- LAST but not Least: Online Spanners for Buy-at-Bulk
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
- On Hierarchical Routing in Doubling Metrics
- Greedy spanners are optimal in doubling metrics
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
This page was built for publication: Bounded-degree light approximate shortest-path trees in doubling metrics
