HLINĚNÝ, Petr and Carsten THOMASSEN. Deciding Parity of Graph Crossing Number. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2018, vol. 32, No 3, p. 1962-1965. ISSN 0895-4801. Available from: https://dx.doi.org/10.1137/17M1137231.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Deciding Parity of Graph Crossing Number
Authors HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Carsten THOMASSEN (208 Denmark).
Edition SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2018, 0895-4801.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 0.843
RIV identification code RIV/00216224:14330/18:00101456
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1137/17M1137231
UT WoS 000450810500020
Keywords in English graph; crossing number; NP-hardness
Tags formela-journal
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Changed: 16/4/2020 09:54.
Abstract
We prove that it is NP-hard to determine whether the crossing number of an input graph is even or odd.
Abstract (in Czech)
Dokazujeme, že je NP-těžké rozlišit, zda průsečíkové číslo daného grafu je liché nebo sudé.
Links
GA17-00837S, research and development projectName: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech
Investor: Czech Science Foundation
PrintDisplayed: 15/6/2024 15:23