Detailed Information on Publication Record
2006
Crossing Number is Hard for Cubic Graphs
HLINĚNÝ, PetrBasic information
Original name
Crossing Number is Hard for Cubic Graphs
Name in Czech
Průsečíkové číslo je těžké pro kubické grafy
Authors
HLINĚNÝ, Petr (203 Czech Republic, guarantor)
Edition
Journal of Combinatorial Theory, Ser B, Amsterdam, Elsevier B.V. 2006, 0095-8956
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10101 Pure mathematics
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
References:
Impact factor
Impact factor: 0.792
RIV identification code
RIV/00216224:14330/06:00015568
Organization unit
Faculty of Informatics
UT WoS
000238399000002
Keywords in English
crossing number; cubic graph; NP-completeness
Tags
International impact, Reviewed
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.
In Czech
[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.
Links
| GA201/05/0050, research and development project |
| ||
| MSM0021622419, plan (intention) |
|