Colloquium of Research Area KL - siebtes Kolloquium
Colloquium of Research Area KL - siebtes Kolloquium

7th Colloquium of Research Area KL

Date: February 3, 2017

Venue:  Seminar room 1st floor, Arithmeum, Lennéstr. 2, Bonn

Homepage: Research Institute for Discrete Mathematics


15:45 Coffee and Tee (Lounge 2nd floor, Arithmeum, Lennéstr. 2)
16:15 Stefan Kratsch: Preprocessing for Vertex Cover: A brief introduction to kernelization
17:00 Coffee break
17:30 Dirk Müller: Timing-constrained global routing
  After the Colloquium there will be the opportunity to have dinner together


Stefan Kratsch: Preprocessing for Vertex Cover: A brief introduction to kernelization

The talk will give an introduction to the notion of kernelization from parameterized complexity. Kernelization is a formal definition for efficient preprocessing, aimed in particular at NP-hard problems, and has allowed for the development of a rich theory with upper and lower bounds. Parameterized complexity generally seeks a more fine-grained complexity analysis of computationally hard problems by relating time and space requirements to both the input size and one or more problem-specific parameters.


For illustration we will focus on the pivotal Vertex Cover problem. Depending on the considered parameter, this problem exhibits different degrees of parameterized (in-)tractability and different degrees of feasibility of preprocessing. In particular, Vertex Cover has seen the greatest success in getting faster algorithms and better preprocessing through studying harder problem parameters. The study of this problem brings together many classic results from graph theory, optimization, and matroids.


Dirk Müller: Timing-constrained global routing

We show how to incorporate global static timing constraints into global routing. Our approach is based on the min-max resource sharing model that proved successful for global routing in theory and practice. Static timing constraints are modeled by a linear number of additional resources and customers. The algorithm dynamically adjusts delay budgets and can, thus, trade off wiring congestion for delay. 


As a subroutine, the algorithm routes a single net. If this subroutine is near-optimal, we will find near-optimal solutions for the overall problem very efficiently. The approach works for many delay models; here we discuss a linear delay model (before buffering) and the Elmore delay model (after buffering). We demonstrate the benefit of our timing-constrained global routing algorithm by experimental results on industrial chips.


This is joint work with Stephan Held, Daniel Rotter, Rudolf Scheifele, Vera Traub, and Jens Vygen.