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, 2018, roč. 32, č. 3, s. 1962-1965. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/17M1137231.

Základní údaje

Originální název

Deciding Parity of Graph Crossing Number

Autoři

HLINĚNÝ, Petr ORCID a Carsten THOMASSEN

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2018, 0895-4801

---

Další údaje

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í

Odkazy

URL

Impakt faktor

Impact factor: 0.843

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/18:00101456

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1137/17M1137231

UT WoS

000450810500020

EID Scopus

2-s2.0-85053940046

Klíčová slova anglicky

graph; crossing number; NP-hardness

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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

Č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