DOI

We study the computational complexity of the hamiltonian cycle problem in the class of graphs of vertex degree at most 3. Our goal is to distinguish boundary properties of graphs that make the problem difficult (NP-complete) in this domain. In the present paper, we discover the first boundary class of graphs for the hamiltonian cycle problem in subcubic graphs. © 2010 Springer-Verlag.
Язык оригиналаанглийский
Название основной публикацииTheory and Applications of Models of Computation (TAMC 2010)
Страницы320-327
Число страниц8
DOI
СостояниеОпубликовано - 15 июл 2010

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ИздательSpringer Nature
Том6108
ISSN (печатное издание)0302-9743

ID: 127758076