Buffered Steiner trees for difficult instances

C. J. Alpert, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar, A. J. Sullivan, P. Villarrubia

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations


Buffer insertion has become an increasingly critical optimization in high performance design. The problem of finding a delay-optimal buffered Steiner tree has been an active area of research, and excellent solutions exist for most instances. However, current approaches fail to adequately solve a particular class of real-world "difficult" instances which are characterized by a large number of sinks, variations in sink criticalities, and varying polarity requirements. We propose a new Steiner tree construction called C-Tree for these instance types. When combined with van Ginneken style buffer insertion, C-Tree achieves higher quality solutions with fewer resources compared to traditional approaches.

Original languageEnglish (US)
Title of host publicationProceedings of the International Symposium on Physical Design
Number of pages6
StatePublished - Jan 1 2001
Event2001 International Symposium on Physical Design - Sonoma, CA, United States
Duration: Apr 1 2001Apr 4 2001


Other2001 International Symposium on Physical Design
Country/TerritoryUnited States
CitySonoma, CA


Dive into the research topics of 'Buffered Steiner trees for difficult instances'. Together they form a unique fingerprint.

Cite this