Back to Search Start Over

Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem.

Authors :
Yen Hung Chen
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