![Důležité termíny](https://cdn.muni.cz/media/3633704/image_2.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
Crossing Number is Hard for Kernelization
Název česky | Průsečíkové číslo je těžké kernelizovat |
---|---|
Autoři | |
Rok publikování | 2016 |
Druh | Článek ve sborníku |
Konference | 32nd International Symposium on Computational Geometry (SoCG 2016) |
Fakulta / Pracoviště MU | |
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: |