On component-size bounded Steiner trees

DOI10.1016/0166-218X(94)00045-FzbMath0827.05018MaRDI QIDQ1894356

Ding-Zhu Du

Publication date: 24 July 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

metric spaceSteiner treeSteiner ratio

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Related Items (5)

A better constant-factor approximation for selected-internal Steiner minimum tree ⋮ An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree ⋮ Approximating the selected-internal Steiner tree ⋮ On the terminal Steiner tree problem.

Cites Work

• The Steiner problem with edge lengths 1 and 2
• The Steiner problem in phylogeny is NP-complete
• The Steiner ratio conjecture for six points
• An 11/6-approximation algorithm for the network Steiner problem
• On Steiner Minimal Trees with Rectilinear Distance
• `` Strong NP-Completeness Results
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Steiner Minimal Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On component-size bounded Steiner trees