Comparison of formulations and a heuristic for packing Steiner trees in a graph

Sunil Chopra*

*Corresponding author for this work

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

In this paper, we consider the problem of packing Steiner trees in a graph. This problem arises during the global routing phase of circuit layout design. We consider various integer programming formulations and rank them according to lower bounds they provide as LP-relaxations. We discuss a solution procedure to obtain both lower and upper bounds using one of the LP-relaxations. Computational results to test the effectiveness of our procedures are provided.

Original languageEnglish (US)
Pages (from-to)143-171
Number of pages29
JournalAnnals of Operations Research
Volume50
Issue number1
DOIs
StatePublished - Dec 1 1994

Keywords

  • LP-relaxation
  • Steiner tree
  • packing

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Comparison of formulations and a heuristic for packing Steiner trees in a graph'. Together they form a unique fingerprint.

Cite this