An Improved Approximation Algorithm for the Terminal Steiner Tree Problem

University of Taipei > 理學院 > 資訊科學系 > 會議論文 > Item 987654321/4714

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/4714

题名:	An Improved Approximation Algorithm for the Terminal Steiner Tree Problem
作者:	Yen Hung Chen 陳彥宏
贡献者:	臺北市立教育大學資訊科學系
关键词:	Approximation algorithms NP-complete Steiner tree terminal Steiner tree problem telecommunications evolutionary tree reconstruction in biology
日期:	2011
上传时间:	2011-12-01 10:08:53 (UTC+8)
摘要:	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.
關聯:	Computational Science and Its Applications - ICCSA 2011 Volume 6784/2011 P.141-151
显示于类别:	[資訊科學系] 會議論文

文件中的档案:

没有与此文件相关的档案.

检视Licence

在uTaipei中所有的数据项都受到原著作权保护.