Faster computer chips via graph theory

Another "Best Paper Award" for Discrete Mathematics in Bonn

The Bonn master student Benjamin Rockel and his supervisor Stephan Held, a professor at the Research Institute for Discrete Mathematics, received a Best Paper Award at the Design Automation Conference in San Francisco, a world-leading chip design conference. The work entitled "Exact Algorithms for Delay-Constrained Steiner Arborescences" deals with the fast, resource-efficient distribution of signals on a chip.

Chip design uses tools from graph theory: directed tree structures, so-called Steiner arborescences. The aim is to optimally distribute the signals using such arborescences. Optimal means that the signal transmission should, of course, be as fast as possible, but also resource-saving regarding power consumption. A partial problem within this method is how to optimally embed a Steiner arborescence in the two-dimensional plane. Here, the work of Benjamin Rockel and Stephan Held begins: The two Bonn scientists model the problem as a network flow problem in which the edges of the arborescence are loaded with weights (costs). Thus, the search for an optimal tree topology can be improved and the runtime of the entire algorithm considerably decreases.

Awarded Paper:

Held, Stephan; Rockel, Benjamin (2018) "Exact Algorithms for Delay-bounded Steiner Arborescences", Proceedings of the 55th Annual Design Automation Conference 44:1-44:6, DOI:10.1145/3195970.3196048