Back to Search
Start Over
Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem.
- Source :
- Journal of Applied Mathematics; 2012, p1-8, 8p
- Publication Year :
- 2012
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 1110757X
- Database :
- Complementary Index
- Journal :
- Journal of Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 84861716
- Full Text :
- https://doi.org/10.1155/2012/394721