A note on the terminal Steiner tree problem
A note on the terminal Steiner tree problem.
Published in: Information Processing Letters Vol. 87 (4). pp. 219-220.
Lin and Xue introduced a variant of the graph Steiner tree problem, in which each terminal vertex is required to be a leaf in the solution Steiner tree. They present a ho + 2 approximation algorithm, where ho is the approximation ratio of the best known efficient algorithm for the regular graph Steiner tree problem. In this note, we derive a simplified algorithm with an improved approximation ratio of 2 ho (currently ho approx 1.550 )
|Citations:||0 (Google Scholar) | 7 (Web of Science)|
|Uncontrolled Keywords:||Approximation algorithms Steiner minimum tree Terminal Steiner tree|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
Mathematical Institute > Prof. Dr. Faigle
|Depositing User:||Bernhard Fuchs|
|Date Deposited:||10 Sep 2003 00:00|
|Last Modified:||17 Aug 2011 09:26|