𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Algorithmic Framework for the Exact Solution of the Prize-Collecting Steiner Tree Problem

✍ Scribed by Ivana Ljubić; René Weiskircher; Ulrich Pferschy; Gunnar W. Klau; Petra Mutzel; Matteo Fischetti

Publisher
Springer-Verlag
Year
2005
Tongue
English
Weight
369 KB
Volume
105
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Variations of the prize-collecting Stein
Variations of the prize-collecting Steiner tree problem
✍ Olena Chapovska; Abraham P. Punnen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB

## Abstract The prize‐collecting Steiner tree problem is well known to be NP‐hard. We consider seven variations of this problem generalizing several well‐studied bottleneck and minsum problems with feasible solutions as trees of a graph. Four of these problems are shown to be solvable in __O__(__m_

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