Publications
Detailed Information
A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hong, Sung-Pil | - |
dc.contributor.author | Chung, Sung-Jin | - |
dc.contributor.author | Park, Bum Hwan | - |
dc.date.accessioned | 2009-07-10T07:55:29Z | - |
dc.date.available | 2009-07-10T07:55:29Z | - |
dc.date.issued | 2003-10-10 | - |
dc.identifier.citation | Oper. Res. Lett. 32 (3) (2004) 233-239 | en |
dc.identifier.issn | 0167-6377 | - |
dc.identifier.uri | https://hdl.handle.net/10371/5347 | - |
dc.description.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. | en |
dc.language.iso | en | - |
dc.publisher | Elsevier | en |
dc.subject | Spanning tree | en |
dc.subject | Bicriteria approximation | en |
dc.subject | Fully polynomial approximation scheme | en |
dc.subject | Matrix-tree theorem | en |
dc.title | A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem | en |
dc.type | Article | en |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.contributor.AlternativeAuthor | 정성진 | - |
dc.contributor.AlternativeAuthor | 박범환 | - |
dc.identifier.doi | 10.1016/j.orl.2003.06.003 | - |
dc.identifier.doi | 10.1016/j.orl.2003.06.003 | - |
dc.citation.journaltitle | Operations Research Letters | - |
- Appears in Collections:
- 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.