Deciding Parity of Graph Crossing Number

HLINĚNÝ, Petr a Carsten THOMASSEN. Deciding Parity of Graph Crossing Number. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, roč. 32, č. 3, s. 1962-1965. ISSN 0895-4801. doi:10.1137/17M1137231. 2018.

Základní údaje

• Originální název: Deciding Parity of Graph Crossing Number
• Autoři: HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Carsten THOMASSEN (208 Dánsko).
• Vydání: SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2018, 0895-4801.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Spojené státy
• Utajení: není předmětem státního či obchodního tajemství
• WWW: URL
• Impakt faktor: Impact factor: 0.843
• Kód RIV: RIV/00216224:14330/18:00101456
• Organizační jednotka: Fakulta informatiky
• Doi: http://dx.doi.org/10.1137/17M1137231
• UT WoS: 000450810500020
• Klíčová slova anglicky: graph; crossing number; NP-hardness
• Štítky: formela-journal
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

We prove that it is NP-hard to determine whether the crossing number of an input graph is even or odd.

Anotace česky

Dokazujeme, že je NP-těžké rozlišit, zda průsečíkové číslo daného grafu je liché nebo sudé.

Návaznosti

• GA17-00837S, projekt VaV: Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems