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

DOI10.1016/S0020-0190(98)00201-4zbMATH Open1339.68209MaRDI QIDQ294609FDOQ294609

Guohui Lin, Guoliang Xue

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

Recommendations

• Approximations for Steiner trees with minimum number of Steiner points
• An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
• Approximations for Steiner trees with minimum number of Steiner points
• On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
• scientific article; zbMATH DE number 1796993

zbMATH Keywords

approximation algorithmswireless communicationsSteiner minimum treesVLSI designWDM 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)

Cites Work

• Title not available (Why is that?)
• The Steiner tree problem
• Steiner Minimal Trees
• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• On Minimum Cost Networks with Nonlinear Costs
• The Complexity of Computing Steiner Minimal Trees
• Bottleneck Steiner trees in the plane

Cited In (31)

• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• The subdivision-constrained routing requests problem
• Improved approximation algorithms for single-tiered relay placement
• Minimum Steiner trees on a set of concyclic points and their center
• The Euclidean bottleneck full Steiner tree problem
• Relay placement for fault tolerance in wireless networks in higher dimensions
• Constrained relay node deployment for underwater acoustic wireless sensor networks
• Approximations for Steiner trees with minimum number of Steiner points
• Relay placement for two-connectivity
• A Sensor Deployment Strategy in Bus-Based Hybrid Ad-Hoc Networks
• Title not available (Why is that?)
• Optimal relay node placement in delay constrained wireless sensor network design
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\)
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
• Optimal deployment of indoor wireless local area networks
• Title not available (Why is that?)
• Approximations for constructing tree-form structures using specific material with fixed length
• Wire segmenting for buffer insertion based on RSTP-MSP
• Approximations for Steiner trees with minimum number of Steiner points
• Spatio-temporal multi-robot routing
• Optimal relay location for resource-limited energy-efficient wireless communication
• Wireless networking, dominating and packing
• Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
• Combination algorithms for Steiner tree variants
• Approximation algorithms for constructing some required structures in digraphs
• Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree
• Approximating minimum Steiner point trees in Minkowski planes
• The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition
• An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane

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

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