Deciding Parity of Graph Crossing Number

• 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
• 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

• Structural properties, parameterized tractability and hardness in combinatorial problems