An approximation algorithm to the k-Steiner forest problem

DOI10.1016/J.TCS.2008.10.033MaRDI QIDQ1007251zbMATH OpenOpenAlexFDO

Authors Peng Zhang, Mingji Xia

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)

Recommendations

• An Approximation Algorithm to the k-Steiner Forest Problem
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
• A primal-dual approximation algorithm for the Steiner forest problem
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach

Cites work

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

Cited in

(10)

• Approximation algorithms for Steiner forest: An experimental study
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• Greedy algorithms for Steiner forest
• Approximating \(k\)-forest with resource augmentation: a primal-dual approach
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• Improved Approximation Algorithm for Steiner k -Forest with Nearly Uniform Weights
• Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing
• An Approximation Algorithm to the k-Steiner Forest Problem

This page was built for publication: An approximation algorithm to the \(k\)-Steiner forest problem

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