Hamiltonian cycles in subcubic graphs: what makes the problem difficult

Korpelainen, Nicholas; Lozin, Vadim V. and Tiskin, Alexander (2010). Hamiltonian cycles in subcubic graphs: what makes the problem difficult. In: Theory and Applications of Models of Computation, Springer, pp. 320–327.

DOI: https://doi.org/10.1007/978-3-642-13562-0_29

Abstract

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.

Viewing alternatives

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations