Thek-Steiner Ratio in Graphs

DOI10.1137/S0097539795281086zbMath0870.68109MaRDI QIDQ4337667

Al Borchers, Ding-Zhu Du

Publication date: 26 May 1997

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

zbMATH Keywords

graph theorygraph algorithmsSteiner minimum treeapproximation algorithmsSteiner treesSteiner ratio

Mathematics Subject Classification ID

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

Related Items (29)

Improved approximation algorithms for single-tiered relay placement ⋮ A better constant-factor approximation for selected-internal Steiner minimum tree ⋮ On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree ⋮ Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem ⋮ Chvátal-Gomory cuts for the Steiner tree problem ⋮ Robust reoptimization of Steiner trees ⋮ On the low-dimensional Steiner minimum tree problem in Hamming metric ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ 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 ⋮ T-joins in strongly connected hypergraphs ⋮ (1 + ρ)-Approximation for Selected-Internal Steiner Minimum Tree ⋮ Unnamed Item ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Combination algorithms for Steiner tree variants ⋮ Approximations for node-weighted Steiner tree in unit disk graphs ⋮ An Efficient Approximation Algorithm for the Steiner Tree Problem ⋮ An improved algorithm for the Steiner tree problem with bounded edge-length ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ A partition-based relaxation for Steiner trees ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ The full Steiner tree problem ⋮ Performance evaluation for energy efficient topologic control in ad hoc wireless networks ⋮ Approximating the selected-internal Steiner tree ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ On the terminal Steiner tree problem.

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