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

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

0.00 Avg rating0 Votes
Article ID: iaor1995708
Country: Switzerland
Volume: 50
Issue: 1
Start Page Number: 143
End Page Number: 171
Publication Date: Sep 1994
Journal: Annals of Operations Research
Authors:
Keywords: Steiner problem
Abstract:

In this paper, the problem of packing Steiner trees in a graph is considered. This problem arises during the global routing phase of circuit layout design. Various integer programming formulations are considered and ranked according to lower bounds they provide as LP-relaxations. A solution procedure to obtain both lower and upper bounds using one of the LP-relaxations is discussed. Computational results to test the effectiveness of the present procedures are provided.

Reviews

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