2015
On Hardness of the Joint Crossing Number
HLINĚNÝ, Petr a Gelasio SALAZARZákladní údaje
Originální název
On Hardness of the Joint Crossing Number
Autoři
HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Gelasio SALAZAR (484 Mexiko)
Vydání
LNCS 9472. Berlin, International Symposium on Algorithms and Computation (ISAAC 2015), Lecture Notes in Computer Science 9472, od s. 603-613, 11 s. 2015
Nakladatel
Springer Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14330/15:00081412
Organizační jednotka
Fakulta informatiky
ISBN
978-3-662-48970-3
ISSN
UT WoS
000375151300051
Klíčová slova anglicky
joint crossing number; crossing minimization
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 14. 2. 2017 08:58, prof. RNDr. Petr Hliněný, Ph.D.
V originále
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minimized. It was introduced by Negami in 2001 in connection with diagonal flips in triangulations of surfaces, and subsequently investigated in a general form for small-genus surfaces. We prove that all of the commonly considered variants of this problem are NP-hard already in the orientable surface of genus 6, by a reduction from a special variant of the anchored crossing number problem of Cabello and Mohar.
Česky
Dokazujeme těžkost problému souběžného nakreslení dvou grafů na stejnou plochu rodu 6 s minimem vzájemných průsečíků.
Návaznosti
| GBP202/12/G061, projekt VaV |
|