Journal of Applied Mathematics
Volume 2012 (2012), Article ID 394721, 8 pages
http://dx.doi.org/10.1155/2012/394721
Research Article

Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem

Yen Hung Chen

Department of Computer Science, Taipei Municipal University of Education, No. 1, Ai-Guo West Road, Taipei 10048, Taiwan

Received 28 October 2011; Accepted 18 January 2012

Academic Editor: Rudong Chen

Copyright © 2012 Yen Hung Chen. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Let 𝐺 = ( 𝑉 , 𝐸 ) 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.