2006
Crossing Number is Hard for Cubic Graphs
HLINĚNÝ, PetrZákladní údaje
Originální název
Crossing Number is Hard for Cubic Graphs
Název česky
Průsečíkové číslo je těžké pro kubické grafy
Autoři
HLINĚNÝ, Petr (203 Česká republika, garant)
Vydání
Journal of Combinatorial Theory, Ser B, Amsterdam, Elsevier B.V. 2006, 0095-8956
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10101 Pure mathematics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 0.792
Kód RIV
RIV/00216224:14330/06:00015568
Organizační jednotka
Fakulta informatiky
UT WoS
000238399000002
Klíčová slova anglicky
crossing number; cubic graph; NP-completeness
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 19. 12. 2006 13:23, prof. RNDr. Petr Hliněný, Ph.D.
V originále
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.
Česky
[Garey and Johnson, 1983] dikázali, že výpočet průsečíkového čísla grafu je NP-těžký problém. Jejich redukce však používá paralelní hrany a velmi vysoké stupně vrcholů. My dokazujeme, že je NP-těžké vypočítat průsečíkové číslo jednoduchého š-souvislého kubického grafu. To mimo jiné ukazuje těžkost výpočtu minorově-monotónního průsečíkového čísla, což byla dosud otevřená otázka.
Návaznosti
| GA201/05/0050, projekt VaV |
| ||
| MSM0021622419, záměr |
|