A note on the terminal Steiner tree problem

Fuchs, Bernhard (2003) A note on the terminal Steiner tree problem.
Published in: Information Processing Letters Vol. 87 (4). pp. 219-220.

Abstract

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 )


Actions:
Full text not available from this repository.
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2003-458
Depositing User: Bernhard Fuchs
Date Deposited: 10 Sep 2003 00:00
Last Modified: 17 Aug 2011 09:26
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/458