A branch and cut algorithm for the Steiner problem in graphs

A branch and cut algorithm for the Steiner problem in graphs

0.00 Avg rating0 Votes
Article ID: iaor20022458
Country: United States
Volume: 31
Issue: 1
Start Page Number: 39
End Page Number: 59
Publication Date: Jan 1998
Journal: Networks
Authors: ,
Keywords: Steiner problem
Abstract:

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 constraints given previously in the literature. We strengthen this SST formulation and present a branch and cut algorithm to solve the problem to optimality. This algorithm incorporates reduction tests and is used to solve a number of problems drawn from the literature. A number of general issues relating to branch and cut algorithms are also highlighted.

Reviews

Required fields are marked *. Your email address will not be published.