direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Losing Weights

Till Fluschnik (TU Berlin)


Efficient data preprocessing with guarantees, called kernelization, plays a central role in parameterized algorithmics. Herein, one aims for shrinking the size of an input instance of a parameterized problem in polynomial time such that the size can be upper-bounded by some function (preferably a polynomial) only depending on the parameter. For several parameterized problems, information on parts of the input (e.g. number of degree-one neighbors) can be expressed through (vertex-)weights. Hereby, the original instance size can be shrunk (e.g. deleting degree-one vertices). However, (vertex-)weights are introduced that are not necessarily upper-bounded by the parameter. In this talk, we describe and exemplify a technique due to Frank and Tardos [Combinatorica'87] to shrink the introduced weights to obtain (polynomial) kernelizations.


Till Fluschnik
TEL 512

Back to the research colloquium site.

Nach oben

Zusatzinformationen / Extras