Crossing Number is Hard for Cubic Graphs

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é pro kubické grafy
Autoři	HLINĚNÝ Petr
Rok publikování	2006
Druh	Článek v odborném periodiku
Časopis / Zdroj	Journal of Combinatorial Theory, Ser B
Fakulta / Pracoviště MU	Fakulta informatiky
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:	Vysoce paralelní a distribuované výpočetní systémy