Deciding Parity of Graph Crossing Number

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	HLINĚNÝ Petr THOMASSEN Carsten
Rok publikování	2018
Druh	Článek v odborném periodiku
Časopis / Zdroj	SIAM Journal on Discrete Mathematics
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	https://www.fi.muni.cz/~hlineny/papers/paritycross-SIAM.pdf
Doi	https://doi.org/10.1137/17M1137231
Klíčová slova	graph; crossing number; NP-hardness
Popis	Dokazujeme, že je NP-těžké rozlišit, zda průsečíkové číslo daného grafu je liché nebo sudé.
Související projekty:	Structural properties, parameterized tractability and hardness in combinatorial problems