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

DOI10.1016/J.TCS.2019.12.012MaRDI QIDQ2201993zbMATH OpenOpenAlexWikidataFDO

Authors Wei Ding, Ke Qiu

Publication date 17 September 2020

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

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

zbMATH Keywords

diameterperturbation\(k\)-Steiner forest

Mathematics Subject Classification ID

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

Recommendations

• Minimum diameter \(k\)-Steiner forest
• Algorithms for the minimum diameter terminal Steiner tree problem
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem
• Diameter-constrained Steiner tree
• Minimum diameter vertex-weighted Steiner tree

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A distributed algorithm for constructing a minimum diameter spanning tree
• A heuristic for the p-center problem in graphs
• A primal-dual approximation algorithm for the Steiner forest problem
• Algorithms for the minimum diameter terminal Steiner tree problem
• An approximation algorithm to the \(k\)-Steiner forest problem
• Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Dial a Ride from k-Forest
• Generalized Steiner problem in outerplanar networks
• Generalized steiner problem in series-parallel networks
• Improved approximation algorithm for Steiner \(k\)-Forest with nearly uniform weights
• Minimum diameter \(k\)-Steiner forest
• On the minimum diameter spanning tree problem
• Some generalizations of the steiner problem in graphs
• Steiner tree problems in computer communication networks.
• 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

(8)

• Minimum diameter vertex-weighted Steiner tree
• The weighted \(k\)-center problem in trees for fixed \(k\)
• Placing Green bridges optimally, with a multivariate analysis
• Minimum diameter \(k\)-Steiner forest
• Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs
• Algorithms for the minimum diameter terminal Steiner tree problem
• A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees
• Placing green bridges optimally, with a multivariate analysis

This page was built for publication: A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem

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