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

Sunil Chopra*, Edgar R. Gorres, M. R. Rao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

60 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)320-335
Number of pages16
JournalORSA journal on computing
Volume4
Issue number3
DOIs
StatePublished - Jan 1 1992

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Solving the Steiner tree problem on a graph using branch and cut'. Together they form a unique fingerprint.

Cite this