Hamiltonian cycles in subcubic graphs: What makes the problem difficult

DOI

https://doi.org/10.1007/978-3-642-13562-0_29
Final published version

Nicholas Korpelainen
Vadim V. Lozin
Alexander Tiskin

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.

Original language	English
Title of host publication	Theory and Applications of Models of Computation (TAMC 2010)
Pages	320-327
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-642-13562-0_29
State	Published - 15 Jul 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Nature
Volume	6108
ISSN (Print)	0302-9743

ID: 127758076