DIAMETER-CONSTRAINED STEINER TREES

DOI10.1142/S179383091100136XzbMath1252.68350OpenAlexW2026680711MaRDI QIDQ2905280

Guoliang Xue, Wei Ding, Guo-Hui Lin

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Minimum diameter cost-constrained Steiner trees ⋮ Minimum diameter vertex-weighted Steiner tree

Cites Work

• Unnamed Item
• 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
• On approximation algorithms for the terminal Steiner tree problem
• The Steiner tree problem
• A polynomial time approximation scheme for minimum cost delay-constrained multicast tree under a Steiner topology
• On the terminal Steiner tree problem.
• 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

This page was built for publication: DIAMETER-CONSTRAINED STEINER TREES