Bounded Degree Group Steiner Tree Problems

DOI10.1007/978-3-030-48966-3_26MaRDI QIDQ5041204zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, Zeev Nutov

Publication date 13 October 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• The minimum degree group Steiner problem
• On approximating degree-bounded network design problems
• On approximating degree-bounded network design problems
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• On some network design problems with degree constraints

Cites work

• O(^2 k/ k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A greedy approximation algorithm for the group Steiner problem
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A tight bound on approximating arbitrary metrics by tree metrics
• An improved approximation scheme for the Group Steiner Problem
• Approximating the weight of shallow Steiner trees
• Approximation Algorithms for Directed Steiner Problems
• Beyond metric embedding: approximating group Steiner trees on bounded treewidth graphs
• Greedy algorithms for online survivable network design
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Information Dissemination in Trees
• Iterative methods in combinatorial optimization.
• Multicommodity facility location under group Steiner access cost
• Online degree-bounded Steiner network design
• Online weighted degree-bounded Steiner networks via novel online mixed packing/covering
• Polylogarithmic inapproximability
• Saving an epsilon: a 2-approximation for the k-MST problem in graphs

Cited in

(7)

• Solving group Steiner problems as Steiner problems.
• The minimum degree group Steiner problem
• On approximating degree-bounded network design problems
• Some formulations for the group Steiner tree problem
• On approximating degree-bounded network design problems
• Fast combinatorial algorithms for efficient sortation
• Fast combinatorial algorithms for efficient sortation

This page was built for publication: Bounded Degree Group Steiner Tree Problems

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