Steiner tree problem with minimum number of Steiner points and bounded edge-length

DOI10.1016/S0020-0190(98)00201-4zbMath1339.68209MaRDI QIDQ294609

Guoliang Xue, Guo-Hui Lin

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098002014?np=y

zbMATH Keywords

VLSI designwireless communicationsapproximation algorithmsSteiner minimum treesWDM optimal networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (27)

Improved approximation algorithms for single-tiered relay placement ⋮ Optimal relay node placement in delay constrained wireless sensor network design ⋮ CONSTRAINED RELAY NODE DEPLOYMENT FOR UNDERWATER ACOUSTIC WIRELESS SENSOR NETWORKS ⋮ 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 ⋮ A Sensor Deployment Strategy in Bus-Based Hybrid Ad-Hoc Networks ⋮ Spatio-temporal multi-robot routing ⋮ Optimal deployment of indoor wireless local area networks ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ Optimal relay location for resource-limited energy-efficient wireless communication ⋮ Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\) ⋮ The subdivision-constrained routing requests problem ⋮ Combination algorithms for Steiner tree variants ⋮ The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition ⋮ Wireless networking, dominating and packing ⋮ Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree ⋮ Approximation algorithms for constructing some required structures in digraphs ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ Improving construction for connected dominating set with Steiner tree in wireless sensor networks ⋮ Approximations for Steiner trees with minimum number of Steiner points ⋮ Wire segmenting for buffer insertion based on RSTP-MSP ⋮ Approximating minimum Steiner point trees in Minkowski planes ⋮ Algorithms for connected set cover problem and fault-tolerant connected set cover problem ⋮ Approximation algorithms for constructing required subgraphs using stock pieces of fixed length ⋮ Relay placement for two-connectivity ⋮ An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane ⋮ A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points

Cites Work

• Unnamed Item
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• The Steiner tree problem
• On Minimum Cost Networks with Nonlinear Costs
• The Complexity of Computing Steiner Minimal Trees
• Bottleneck Steiner trees in the plane
• Steiner Minimal Trees

This page was built for publication: Steiner tree problem with minimum number of Steiner points and bounded edge-length