Thek-Steiner Ratio in Graphs

DOI10.1137/S0097539795281086MaRDI QIDQ4337667zbMATHFDO

Authors Al Borchers, Du Ding-Zhu

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

graph theoryapproximation algorithmsgraph algorithmsSteiner treesSteiner minimum treeSteiner ratio

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1263241
• Thek-Steiner Ratio in the Rectilinear Plane
• The Steiner number of a graph
• Steiner Numbers in Graphs
• The Steiner diameter of a graph
• scientific article; zbMATH DE number 4010182
• On the Steiner ratio in \(\mathcal R_n\)
• Bounds on the Steiner radius of a graph
• scientific article; zbMATH DE number 3871417
• scientific article; zbMATH DE number 1355283

Cited in

(31)

• A linear programming based approach to the Steiner tree problem with a fixed number of terminals
• Approximating the selected-internal Steiner tree
• On the low-dimensional Steiner minimum tree problem in Hamming metric
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• On the lossy kernelization for connected treedepth deletion set
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• On the terminal Steiner tree problem.
• New algorithms for Steiner tree reoptimization
• Robust reoptimization of Steiner trees
• (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree
• The Euclidean bottleneck full Steiner tree problem
• Bottleneck Steiner tree with bounded number of Steiner vertices
• Chvátal-Gomory cuts for the Steiner tree problem
• An improved algorithm for the Steiner tree problem with bounded edge-length
• The full Steiner tree problem
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• On component-size bounded Steiner trees
• Node connectivity augmentation via iterative randomized rounding
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• A partition-based relaxation for Steiner trees
• The Clustered Selected-Internal Steiner Tree Problem
• Combination algorithms for Steiner tree variants
• Parameterized study of Steiner tree on unit disk graphs
• Stronger path‐based extended formulation for the Steiner tree problem
• Approximations for node-weighted Steiner tree in unit disk graphs
• Performance evaluation for energy efficient topologic control in ad hoc wireless networks
• Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
• Improved approximation algorithms for single-tiered relay placement
• A better constant-factor approximation for selected-internal Steiner minimum tree
• T-joins in strongly connected hypergraphs
• New algorithms for Steiner tree reoptimization

This page was built for publication: Thek-Steiner Ratio in Graphs

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