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

DOI10.1016/J.TCS.2019.12.012zbMATH Open1455.68275OpenAlexW2995411114WikidataQ126586910 ScholiaQ126586910MaRDI QIDQ2201993FDOQ2201993

Ke Qiu, Wei Ding

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

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

zbMATH Keywords

diameterperturbation\(k\)-Steiner forest

Mathematics Subject Classification ID

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

Cites Work

• A Best Possible Heuristic for the k-Center Problem
• Some generalizations of the steiner problem in graphs
• A heuristic for the p-center problem in graphs
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Steiner tree problems in computer communication networks.
• A primal-dual approximation algorithm for the Steiner forest problem
• On the minimum diameter spanning tree problem
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Dial a Ride from k-Forest
• A distributed algorithm for constructing a minimum diameter spanning tree
• Algorithms for the minimum diameter terminal Steiner tree problem
• Generalized Steiner problem in outerplanar networks
• Generalized steiner problem in series-parallel networks
• 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
• An approximation algorithm to the \(k\)-Steiner forest problem
• Minimum diameter \(k\)-Steiner forest
• Title not available (Why is that?)

Cited In (7)

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

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)