Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem

Yen Hung Chen

Journal of Applied Mathematics, 2012, vol. 2012, issue 1

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.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2012/394721

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2012:y:2012:i:1:n:394721

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().