Thek-Steiner Ratio in Graphs

DOI10.1137/S0097539795281086zbMATH Open0870.68109MaRDI QIDQ4337667FDOQ4337667

Authors: Al Borchers, Du Ding-Zhu 

Publication date: 26 May 1997

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

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

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)

Cited In (31)

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

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)