Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2012/394721 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832560310129524736 |
|---|---|
| author | Yen Hung Chen |
| author_facet | Yen Hung Chen |
| author_sort | Yen Hung Chen |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-50bf600c8ef04ca98a99d3d66d80c50a |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-50bf600c8ef04ca98a99d3d66d80c50a2025-02-03T01:27:50ZengWileyJournal of Applied Mathematics1110-757X1687-00422012-01-01201210.1155/2012/394721394721Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree ProblemYen Hung Chen0Department of Computer Science, Taipei Municipal University of Education, No. 1, Ai-Guo West Road, Taipei 10048, TaiwanLet 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.http://dx.doi.org/10.1155/2012/394721 |
| spellingShingle | Yen Hung Chen Polynomial Time Approximation Schemes for the Constrained Minimum Spanning Tree Problem Journal of Applied Mathematics |
| title | Polynomial Time Approximation Schemes for the Constrained Minimum
Spanning Tree Problem |
| title_full | Polynomial Time Approximation Schemes for the Constrained Minimum
Spanning Tree Problem |
| title_fullStr | Polynomial Time Approximation Schemes for the Constrained Minimum
Spanning Tree Problem |
| title_full_unstemmed | Polynomial Time Approximation Schemes for the Constrained Minimum
Spanning Tree Problem |
| title_short | Polynomial Time Approximation Schemes for the Constrained Minimum
Spanning Tree Problem |
| title_sort | polynomial time approximation schemes for the constrained minimum spanning tree problem |
| url | http://dx.doi.org/10.1155/2012/394721 |
| work_keys_str_mv | AT yenhungchen polynomialtimeapproximationschemesfortheconstrainedminimumspanningtreeproblem |