An Improved Approximation Algorithm for the Terminal Steiner Tree Problem

uTaipei > College of Science > Department of Computer Science > Proceedings > Item 987654321/4714

Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/4714

Title:	An Improved Approximation Algorithm for the Terminal Steiner Tree Problem
Authors:	Yen Hung Chen 陳彥宏
Contributors:	臺北市立教育大學資訊科學系
Keywords:	Approximation algorithms NP-complete Steiner tree terminal Steiner tree problem telecommunications evolutionary tree reconstruction in biology
Date:	2011
Issue Date:	2011-12-01 10:08:53 (UTC+8)
Abstract:	Given a complete graph G = (V,E) with a length function on edges and a subset R of V, the terminal Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the terminal Steiner tree problem is to find a terminal Steiner tree in G with minimum length. In this paper, we present an approximation algorithm with performance ratio 2ρ - (ρα2 - αρ)/(α+α2)(ρ-1)+2(α-1)2 for the terminal Steiner tree problem, where ρ is the best-known performance ratio for the Steiner tree problem with any α ≥ 2. When we let α = 3.87 ≈ 4, this result improves the previous performance ratio of 2.515 to 2.458.
Relation:	Computational Science and Its Applications - ICCSA 2011 Volume 6784/2011 P.141-151
Appears in Collections:	[Department of Computer Science] Proceedings

Files in This Item:

There are no files associated with this item.

View Licence