An approximation algorithm to the k-Steiner forest problem

DOI10.1016/J.TCS.2008.10.033zbMATH Open1169.68053OpenAlexW2176356921MaRDI QIDQ1007251FDOQ1007251

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

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

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)

Cites Work

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• A General Approximation Technique for Constrained Forest Problems
• The dense \(k\)-subgraph problem
• Title not available (Why is that?)
• Improved performance of the greedy algorithm for partial cover
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Saving an epsilon
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Approximation and Online Algorithms
• Master-slave strategy and polynomial approximation
• 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

Cited In (5)

• A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem
• 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)