Thek-Steiner Ratio in Graphs

DOI10.1137/S0097539795281086MaRDI QIDQ4337667zbMATH OpenFDO

Authors Al Borchers, Du Ding-Zhu

Publication date 26 May 1997

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

Full work available at URL https://doi.org/10.1137/S0097539795281086

zbMATH Keywords

approximation algorithmsgraph algorithmsgraph theorySteiner minimum treeSteiner ratioSteiner trees

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 R_n
• Bounds on the Steiner radius of a graph
• scientific article; zbMATH DE number 3871417
• scientific article; zbMATH DE number 1355283

Cited in

(37)

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

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)