Průsečíkové číslo je těžké pro kubické grafy

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00015568" target="_blank" >RIV/00216224:14330/06:00015568 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/61989100:27240/06:00013587
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Crossing Number is Hard for Cubic Graphs
Popis výsledku v původním jazyce
It was proved by [Garey and Johnson, 1983] that computing the crossing number of a graph is an $NP$-hard problem. Their reduction, however, used parallel edges and vertices of very high degrees. We prove here that it is $NP$-hard to determine the crossing number of a simple $3$-connected cubic graph. In particular, this implies that the minor-monotone version of the crossing number problem is also $NP$-hard, which has been open till now.
Název v anglickém jazyce
Crossing Number is Hard for Cubic Graphs
Popis výsledku anglicky
It was proved by [Garey and Johnson, 1983] that computing the crossing number of a graph is an $NP$-hard problem. Their reduction, however, used parallel edges and vertices of very high degrees. We prove here that it is $NP$-hard to determine the crossing number of a simple $3$-connected cubic graph. In particular, this implies that the minor-monotone version of the crossing number problem is also $NP$-hard, which has been open till now.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—

Projekt
<a href="/cs/project/GA201%2F05%2F0050" target="_blank" >GA201/05/0050: Strukturální vlastnosti a algoritmická složitost diskrétních problémů</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2006
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)