On approximating degree-bounded network design problems

DOI10.1007/S00453-022-00924-0MaRDI QIDQ2134742zbMATH OpenOpenAlexFDO

Authors Xiangyu Guo, Guy Kortsarz, B. Laekhanukit, Shi Li, Daniel Vaz, Jiayi Xian

Publication date 3 May 2022

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximationgroupdegreesSteiner

Mathematics Subject Classification ID

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

Recommendations

• On approximating degree-bounded network design problems
• Bounded Degree Group Steiner Tree Problems
• The minimum degree group Steiner problem
• On some network design problems with degree constraints
• \(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm

Cites work

• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• 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
• Additive Approximation for Bounded Degree Survivable Network Design
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation Algorithms for Directed Steiner Problems
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Greedy algorithms for online survivable network design
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• Many birds with one stone
• Online degree-bounded Steiner network design
• Online weighted degree-bounded Steiner networks via novel online mixed packing/covering
• Polylogarithmic inapproximability
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
• Survivable network design with degree or order constraints
• The minimum degree group Steiner problem
• \(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm

Cited in

(5)

• Network Design with Edge-Connectivity and Degree Constraints
• Design networks with bounded pairwise distance
• On approximating degree-bounded network design problems
• Online and approximate network construction from bounded connectivity constraints
• scientific article; zbMATH DE number 6423757 (Why is no real title available?)

This page was built for publication: On approximating degree-bounded network design problems

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