The minimum degree group Steiner problem

DOI10.1016/j.dam.2021.12.003OpenAlexW4200183782MaRDI QIDQ2065790

Zeev Nutov, Guy Kortsarz

Publication date: 13 January 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2021.12.003

zbMATH Keywords

approximationtreewidthgraphsgroupboundedSteiner

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

On approximating degree-bounded network design problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On network design problems: fixed cost flows and the covering steiner problem
• Iterative Methods in Combinatorial Optimization
• Survivable Network Design with Degree or Order Constraints
• Polylogarithmic inapproximability
• Saving an epsilon
• Information Dissemination in Trees
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
• Analytical approach to parallel repetition
• A tight bound on approximating arbitrary metrics by tree metrics