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

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

0.00 Avg rating0 Votes
Article ID: iaor20043261
Country: Netherlands
Volume: 32
Issue: 3
Start Page Number: 233
End Page Number: 239
Publication Date: May 2004
Journal: Operations Research Letters
Authors: , ,
Keywords: networks: path
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.

Reviews

Required fields are marked *. Your email address will not be published.