✦ LIBER ✦

Solving Steiner tree problems in graphs to optimality

✍ Scribed by Koch, T.; Martin, A.

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 261 KB
Volume: 32
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199810)32:3<207::aid-net5>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nearly all problem instances discussed in the literature to optimality, including one problem that-to our knowledge-has not yet been solved. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called SteinLib that is accessible via the World Wide Web.

📜 SIMILAR VOLUMES

A branch-and-cut algorithm for solving g

A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs

✍ Suhl, Uwe H.; Hilbert, Heinrich 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 2 views

Given is an undirected graph with positive or negative edge weights which represent a profit if an investment such as installing a gas pipe takes place in a given time period. A certain part of the graph may already be piped in previous periods. The task is to extend the piped subgraph in the most p

Approximating Steiner trees in graphs wi

Approximating Steiner trees in graphs with restricted weights

✍ Halld�rsson, Magn�s M.; Ueno, Shuichi; Nakao, Hiroshi; Kajitani, Yoji 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 1 views

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d °2. The improvement over other analyzed algorithms is a fac

Tabu search for the Steiner problem in g

Tabu search for the Steiner problem in graphs

✍ Celso C. Ribeiro; Maurício C. De Souza 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB 👁 2 views

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum-weighted subgraph spanning a given subset of nodes (terminals) of the original graph. In this paper, we describe a tabu search algorithm for the Steiner problem in graphs, based o

Optimal tree 3-spanners in directed path

Optimal tree 3-spanners in directed path graphs

✍ Le, Ho�ng-Oanh; Le, Van Bang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB 👁 1 views

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t 3, the case t ϭ 3 still remains open. In this article, we s

A branch and cut algorithm for the Stein

A branch and cut algorithm for the Steiner problem in graphs

✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

The pilot method: A strategy for heurist

The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs

✍ Duin, Cees; Vo�, Stefan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

As a metaheuristic to obtain solutions of enhanced quality, we formulate the so-called pilot method. It is a tempered greedy method that is to avoid the greedy trap by looking ahead for each possible choice (memorizing the best result). Repeatedly, a so-called master solution is modified, each time