Approximation algorithms for priority Steiner tree problems

DOI10.1007/978-3-030-89543-3_10OpenAlexW3210324533MaRDI QIDQ2695278

Faryad Darabi Sahneh, Richard Spence, Stephen G. Kobourov

Publication date: 30 March 2023

Full work available at URL: https://arxiv.org/abs/2108.13544

zbMATH Keywords

network designapproximation algorithmspriority Steiner tree

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Multi-priority graph sparsification

Cites Work

• Unnamed Item
• Unnamed Item
• The Steiner tree problem on graphs: inapproximability results
• The hierarchical network design problem
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Mixed integer programming formulations for Steiner tree and quality of service multicast tree problems
• Improved approximation algorithms for the quality of service multicast tree problem
• Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
• A threshold of ln n for approximating set cover
• Online Priority Steiner Tree Problems
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Dynamic Steiner Tree Problem
• Bicriteria Network Design Problems
• Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• On the approximability of some network design problems
• O (log ² k / log log k )-approximation algorithm for directed Steiner tree
• Analytical approach to parallel repetition
• Steiner Tree Approximation via Iterative Randomized Rounding
• Online Node-Weighted Steiner Tree and Related Problems
• The Multi-Tier Tree Problem
• Grade of service Steiner minimum trees in the Euclidean plane

This page was built for publication: Approximation algorithms for priority Steiner tree problems