An approximation algorithm to the \(k\)-Steiner forest problem

DOI10.1016/j.tcs.2008.10.033zbMath1169.68053OpenAlexW2176356921MaRDI QIDQ1007251

Mingji Xia, Peng Zhang

Publication date: 20 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.033

zbMATH Keywords

approximation algorithmgreedy\(k\)-Steiner forestset \(k\)-cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem

Cites Work

• Unnamed Item
• Improved performance of the greedy algorithm for partial cover
• Master-slave strategy and polynomial approximation
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Saving an epsilon
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
• Approximation and Online Algorithms
• The dense \(k\)-subgraph problem