𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation Algorithms for the Bandwidth Minimization Problem for a Large Class of Trees

✍ Scribed by J. Haralambides

Publisher
Springer
Year
1997
Tongue
English
Weight
327 KB
Volume
30
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Polylogarithmic Approximation Algorith
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
✍ Naveen Garg; Goran Konjevod; R. Ravi πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

A better approximation algorithm for the
A better approximation algorithm for the budget prize collecting tree problem
✍ Asaf Levin πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 206 KB

Given an undirected graph G = (V; E), an edge cost c(e) ¿ 0 for each edge e ∈ E, a vertex prize p(v) ¿ 0 for each vertex v ∈ V , and an edge budget B. The BUDGET PRIZE COLLECTING TREE PROBLEM is to ÿnd a subtree T = (V ; E ) that maximizes v∈V p(v), subject to e∈E c(e) 6 B. We present a (4 + )-appro