The Steiner tree packing problem in VLSI design
Grötschel, Martin
Martin, Alexander (Konrad-Zuse-Zentrum für Informationstechnik Berlin)
Weismantel, Robert

Fecha:	1997
Resumen:	In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing. .
Derechos:	Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.
Lengua:	Anglès
Documento:	Article ; recerca ; Versió publicada
Materia:	Steiner tree packing ; Routing in VLSI design ; Switchbox routing ; Cutting plane algorithm
Publicado en:	Mathematical Programming, vol. 78 n. 2 (1997) p. 265-281, ISSN 0025-5610

17 p, 989.4 KB  Acceso restringido a la UAB

El registro aparece en las colecciones:
Artículos > Artículos de investigación
Artículos > Artículos publicados