Research Institute for Discrete Mathematics


Deutsche Version | Home page of the institute

The institute's central research activities focus on the area of Discrete Mathematics and its applications, particularly on combinatorial optimization and chip design.

Combinatorial Optimization has become more and more important during the last decades, due to its immense significance for application. At the Research Institute for Discrete Mathematics, it has always played a major role. This becomes obvious in the many pioneering works by the institute's scientists and guests, dealing with the most diverse problems in the field of combinatorial optimization. The article [1] gives a brief instruction. The standard work "Combinatorial Optimization" [2], written here, gives a good overview. This book has already five English editions and translations into Japanese, German, French, Italian, Russian, and Chinese. The proceedings [3] of the last Bonn workshop presents current research trends. In June 2014, we hosted IPCO, the leading conference of this field. In fall 2015, there was a HIM trimester program on combinatorial optimization in Bonn.

Chip Design is probably the most interesting and varied range of application of mathematics in general. Modern highly complex chips cannot be designed without the use of methods of discrete mathematics. Many of these methods have been developed at this institute. Long-term industrial cooperations grant us the possibility of working with the latest technologies and the most complex chips. The "BonnTools" [4], which comprise innovative algorithms for placement, routing, timing optimization, clock tree design, and transistor-level layout, are used all over the world. The article [5] gives a brief introduction to chip design. A good survey is given by [6].

Recommended publications in the two main fields of interest:
[1] J. Vygen: Combinatorial Optimization. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download]
[2] B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin, Fifth Edition 2012. [Information]
[3] W.J. Cook, L. Lovász, J. Vygen: Research Trends in Combinatorial Optimization. Springer, Berlin 2009. [Information]
[4] B. Korte, D. Rautenbach, J. Vygen: BonnTools: Mathematical innovation for layout and timing closure of systems on a chip. Proceedings of the IEEE 95 (2007), 555-572 [Download]
[5] S. Held, S. Hougardy, J. Vygen: Chip Design. Princeton Companion of Applied Mathematics, Princeton University Press 2015 [Download]
[6] S. Held, B. Korte, D. Rautenbach, J. Vygen: Combinatorial optimization in VLSI design. In: Combinatorial Optimization: Methods and Applications (V. Chvátal, ed.), IOS Press, Amsterdam 2011, pp. 33-96 [Download]
The sources [2] and [6] contain numerous references to further reading. Besides this, the list of technical reports that have been produced at the institute gives a good impression of the wide range of research activities.

The Research Institute for Discrete Mathematics maintains many international cooperations and third-party projects, amongst which the following are particularly noteworthy: