Approximations for Steiner trees with minimum number of Steiner points

DOI10.1016/S0304-3975(00)00182-1zbMath0983.68140OpenAlexW1983607113MaRDI QIDQ5958113

Donghui Chen, Lusheng Wang, Guo-Hui Lin, Xiao-Dong Hu, Ding-Zhu Du

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00182-1

zbMATH Keywords

VLSI designapproximation algorithmsSteiner treesWDM optical networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items (18)

Improved approximation algorithms for single-tiered relay placement ⋮ Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ Approximations for constructing tree-form structures using specific material with fixed length ⋮ Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces ⋮ Node-weighted Steiner tree approximation in unit disk graphs ⋮ New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs ⋮ (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ Combination algorithms for Steiner tree variants ⋮ A survey on relay placement with runtime and approximation guarantees ⋮ Wireless network design via 3-decompositions ⋮ Wire segmenting for buffer insertion based on RSTP-MSP ⋮ Approximating minimum Steiner point trees in Minkowski planes ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Algorithms for connected set cover problem and fault-tolerant connected set cover problem ⋮ Multicastad hocrouting through mobility-aware Steiner tree meshes with consistency across different mobility models ⋮ Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs ⋮ A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points

Cites Work

• Unnamed Item
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• The Steiner tree problem
• New approximation algorithms for the Steiner tree problems
• Compression theorems and Steiner ratios on spheres
• Approximation schemes for covering and packing problems in image processing and VLSI
• On Minimum Cost Networks with Nonlinear Costs
• The Complexity of Computing Steiner Minimal Trees
• An approximation scheme for some Steiner tree problems in the plane
• Steiner Minimal Trees
• Steiner tree problems

This page was built for publication: Approximations for Steiner trees with minimum number of Steiner points