S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Industrial Engineering (산업공학과) Journal Papers (저널논문_산업공학과)
A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem
- Hong, Sung-Pil; Chung, Sung-Jin; Park, Bum Hwan
- Issue Date
- Oper. Res. Lett. 32 (3) (2004) 233-239
- Spanning tree; Bicriteria approximation; Fully polynomial approximation scheme; Matrix-tree theorem
- 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.
- Files in This Item: There are no files associated with this item.