direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

 

Date
Speaker
Location
Language
20.12.2018
16:00
Till Fluschnik
TEL 512
English

Back to the research colloquium site.

To top

Zusatzinformationen / Extras