Další formáty:
BibTeX
LaTeX
RIS
@article{589862, author = {Hliněný, Petr}, article_location = {Amsterdam}, article_number = {4}, keywords = {crossing number; cubic graph; NP-completeness}, language = {eng}, issn = {0095-8956}, journal = {Journal of Combinatorial Theory, Ser B}, title = {Crossing Number is Hard for Cubic Graphs}, url = {http://dx.doi.org/10.1016/j.jctb.2005.09.009}, volume = {96}, year = {2006} }
TY - JOUR ID - 589862 AU - Hliněný, Petr PY - 2006 TI - Crossing Number is Hard for Cubic Graphs JF - Journal of Combinatorial Theory, Ser B VL - 96 IS - 4 SP - 455-471 EP - 455-471 PB - Elsevier B.V. SN - 00958956 KW - crossing number KW - cubic graph KW - NP-completeness UR - http://dx.doi.org/10.1016/j.jctb.2005.09.009 N2 - 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. ER -
HLINĚNÝ, Petr. Crossing Number is Hard for Cubic Graphs. \textit{Journal of Combinatorial Theory, Ser B}. Amsterdam: Elsevier B.V., roč.~96, č.~4, s.~455-471. ISSN~0095-8956. 2006.
|