Crossing Number is Hard for Cubic Graphs
| Název česky | Průsečíkové číslo je těžké pro kubické grafy |
|---|---|
| Autoři | |
| Rok publikování | 2006 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Combinatorial Theory, Ser B |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1016/j.jctb.2005.09.009 |
| Obor | Obecná matematika |
| Klíčová slova | crossing number; cubic graph; NP-completeness |
| Popis | [Garey and Johnson, 1983] dikázali, že výpočet průsečíkového čísla grafu je NP-těžký problém. Jejich redukce však používá paralelní hrany a velmi vysoké stupně vrcholů. My dokazujeme, že je NP-těžké vypočítat průsečíkové číslo jednoduchého š-souvislého kubického grafu. To mimo jiné ukazuje těžkost výpočtu minorově-monotónního průsečíkového čísla, což byla dosud otevřená otázka. |
| Související projekty: |