✦ LIBER ✦

Variations of the prize-collecting Steiner tree problem

✍ Scribed by Olena Chapovska; Abraham P. Punnen

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 136 KB
Volume: 47
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.20106

No coin nor oath required. For personal study only.

✦ Synopsis

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+n log n) time and the remaining are shown to be NP‐hard where n is the number of nodes and m is the number of edges in the underlying graph. For one of these polynomially solvable cases, we also provide an O(m) algorithm generalizing and unifying known linear time algorithms for the bottleneck spanning tree problem, bottleneck s−t path problem, and bottleneck Steiner tree problem. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 199–205 2006

📜 SIMILAR VOLUMES

Local search with perturbations for the

Local search with perturbations for the prize-collecting Steiner tree problem in graphs

✍ S. A. Canuto; M. G. C. Resende; C. C. Ribeiro 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

The Steiner Tree Problem in Orientation

The Steiner Tree Problem in Orientation Metrics

✍ G.Y. Yan; A. Albrecht; G.H.F. Young; C.K. Wong 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 431 KB

Given a set 3 of : i (i=1, 2, ..., k) orientations (angles) in the plane, one can define a distance function which induces a metric in the plane, called the orientation metric [3]. In the special case where all the angles are equal, we call the metric a uniform orientation metric [2]. Specifically,

Probabilistic models for the Steiner Tre

Probabilistic models for the Steiner Tree problem

✍ Vangelis Th. Paschos; Orestis A. Telelis; Vassilis Zissimopoulos 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB

A tabu search heuristic for the Steiner

A tabu search heuristic for the Steiner Tree Problem

✍ Gendreau, Michel; Larochelle, Jean-Francois; Sans�, Brunilde 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 2 views

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu se

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 branch-and-cut algorithm for the undir

A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem

✍ Jean-François Bérubé; Michel Gendreau; Jean-Yves Potvin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 1 views

## Abstract Given an undirected graph with edge costs and vertex prizes, the aim of the Prize Collecting Traveling Salesman Problem (PCTSP) is to find a simple cycle minimizing the total edge cost while collecting at least a minimum amount of prizes. In this article, we present a branch‐and‐cut alg