J 2018

Deciding Parity of Graph Crossing Number

HLINĚNÝ, Petr a Carsten THOMASSEN

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

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

Impakt faktor

Impact factor: 0.843

Kód RIV

RIV/00216224:14330/18:00101456

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000450810500020

Klíčová slova anglicky

graph; crossing number; NP-hardness

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 16. 4. 2020 09:54, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

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