Diameter-constrained Steiner trees

DOI10.1142/S179383091100136XMaRDI QIDQ2905280zbMATH OpenOpenAlexFDO

Authors Wei Ding, Guohui Lin, Guoliang Xue

Publication date 27 August 2012

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s179383091100136x

zbMATH Keywords

fixed topologyfully polynomial time approximation schemediameter-constrained Steiner tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Diameter-constrained Steiner tree
• Minimum diameter cost-constrained Steiner trees
• On the minimum diameter cost-constrained Steiner tree problem
• A constrained Steiner tree problem
• Minimum diameter vertex-weighted Steiner tree
• Constrained Steiner trees in Halin graphs
• Constrained spanning, Steiner trees and the triangle inequality
• Steiner tree problems
• Steiner tree problems
• When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
• A note on the terminal Steiner tree problem
• A polynomial time approximation scheme for minimum cost delay-constrained multicast tree under a Steiner topology
• An 11/6-approximation algorithm for the network Steiner problem
• An O(pn^ 2) algorithm for the p-median and related problems on tree graphs
• Approximation Schemes for the Restricted Shortest Path Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On approximation algorithms for the terminal Steiner tree problem
• On the terminal Steiner tree problem.
• The Steiner tree problem

Cited in

(6)

• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Constrained spanning, Steiner trees and the triangle inequality
• Steiner Trees for Terminals Constrained to Curves
• Minimum diameter vertex-weighted Steiner tree
• Minimum diameter cost-constrained Steiner trees
• A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees

This page was built for publication: Diameter-constrained Steiner trees

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