SHERP

A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem

Cited 0 time in webofscience Cited 0 time in scopus
Authors
Hong, Sung-Pil; Chung, Sung-Jin; Park, Bum Hwan
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
URI
http://hdl.handle.net/10371/5347
DOI
https://doi.org/10.1016/j.orl.2003.06.003
https://doi.org/10.1016/j.orl.2003.06.003
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse