When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

DOI10.1007/S00224-015-9615-7zbMATH Open1336.05039OpenAlexW2026902273MaRDI QIDQ255267FDOQ255267

Authors: Ali Mashreghi, Alireza Zarei 

Publication date: 9 March 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-015-9615-7

Recommendations

• Diameter-constrained Steiner tree
• Bounded-diameter minimum-cost graph problems
• Minimum diameter cost-constrained Steiner trees
• On the minimum diameter cost-constrained Steiner tree problem
• Minimum diameter vertex-weighted Steiner tree

zbMATH Keywords

approximation algorithmsbicriteria network designbounded diameterminimum Steiner tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distance in graphs (05C12)

Cites Work

• A Greedy Heuristic for the Set-Covering Problem
• VNS and second order heuristics for the min-degree constrained minimum spanning tree problem
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• An improved FPTAS for Restricted Shortest Path.
• Bounded-diameter minimum-cost graph problems
• md-MST is NP-hard for \(d\geq 3\)
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k,2)-Subgraph
• Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Bicriteria Network Design Problems
• The constrained minimum spanning tree problem
• Multicriteria Optimization
• A simple efficient approximation scheme for the restricted shortest path problem
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints

Cited In (7)

• Delay-constrained minimum shortest path trees and related problems
• On the minimum diameter cost-constrained Steiner tree problem
• Diameter-constrained Steiner tree
• Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
• Bounded-diameter minimum-cost graph problems
• Minimum diameter cost-constrained Steiner trees
• Diameter-constrained Steiner trees

This page was built for publication: When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

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