Crossing Number is Hard for Kernelization

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, 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 http://dx.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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.