Crossing Number is Hard for Kernelization

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Průsečíkové číslo je těžké kernelizovat
Autoři	DERŇÁR Marek HLINĚNÝ Petr
Rok publikování	2016
Druh	Článek ve sborníku
Konference	32nd International Symposium on Computational Geometry (SoCG 2016)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://socg2016.cs.tufts.edu/
Doi	https://doi.org/10.4230/LIPIcs.SoCG.2016.42
Obor	Informatika
Klíčová slova	crossing number; kernelization; parameterized complexity
Popis	Dokážeme, že problém průsečíkového čísla grafu nelze polynomiálně kernelizovat, což znamená, že nelze danou instanci v polynomiálním čase převést na ekvivalentní instanci polynomiální velikosti v parametru k.
Související projekty:	Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky Rozsáhlé výpočetní systémy: modely, aplikace a verifikace V. Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity