Solving the Steiner tree problem on a graph using branch and cut

被引：43

作者：

Chopra, Sunil ^{[1
]}

Gorres, Edgar R. ^{[1
]}

Rao, M.R. ^{[1
]}

机构：

[1] Northwestern Univ, Evanston, United States

来源：

ORSA journal on computing | 1992年 / 4卷 / 03期

关键词：

Graph theory - Optimization - Random processes;

D O I：

10.1287/ijoc.4.3.320

中图分类号：

学科分类号：

摘要：

In this paper we report computational experience with a branch and cut solver for the Steiner tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied.

引用

页码：320 / 335