Deciding Parity of Graph Crossing Number

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, 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 http://dx.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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.