direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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. [1]

To top

------ Links: ------

Zusatzinformationen / Extras