Publications
Detailed Information
A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem
Cited 29 time in
Web of Science
Cited 36 time in Scopus
- Authors
- Issue Date
- 2003-10-10
- Publisher
- Elsevier
- Citation
- Oper. Res. Lett. 32 (3) (2004) 233-239
- Keywords
- Spanning tree ; Bicriteria approximation ; Fully polynomial approximation scheme ; Matrix-tree theorem
- Abstract
- We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then utilized to yield a fully polynomial approximation scheme.
- ISSN
- 0167-6377
- Language
- English
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.