Crossing Number is Hard for Kernelization

• 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
• 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

• 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