Polynomial time approximation schemes for the constrained minimum spanning tree problem

uTaipei > College of Science > Department of Computer Science > Periodical Articles > Item 987654321/16013

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

Title:	Polynomial time approximation schemes for the constrained minimum spanning tree problem
Authors:	Chen, Yen-Hung;陳彥宏
Contributors:	臺北市立教育大學資訊科學系
Date:	2012-01
Issue Date:	2017-07-31 13:51:17 (UTC+8)
Abstract:	Let G = (V, E) be an undirected graph with a weight function and a cost function on edges. The constrained minimum spanning tree problem is to find a minimum cost spanning tree T in G such that the total weight in T is at most a given bound B. In this paper, we present two polynomial time approximation schemes (PTASs) for the constrained minimum spanning tree problem.
Relation:	Journal of Applied Mathematics，Vol. 2012，P.1-8
Appears in Collections:	[Department of Computer Science] Periodical Articles

Files in This Item:

There are no files associated with this item.