๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by Sung-Pil Hong; Sung-Jin Chung; Bum Hwan Park

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
213 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

An efficient fully polynomial approximat
An efficient fully polynomial approximation scheme for the Subset-Sum Problem
โœ Hans Kellerer; Renata Mansini; Ulrich Pferschy; Maria Grazia Speranza ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 238 KB

Given a set of n positive integers and a knapsack of capacity c; the Subset-Sum Problem is to find a subset the sum of which is closest to c without exceeding the value c: In this paper we present a fully polynomial approximation scheme which solves the Subset-Sum Problem with accuracy e in time Oรฐm

A Polynomial Time Approximation Scheme f
A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
โœ Bang Ye Wu; Kun-Mao Chao; Chuan Yi Tang ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 155 KB

Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them mult