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

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 38887
• Item Type
• Conference or Workshop Item
• ISBN
• 3-642-13562-5, 978-3-642-13562-0
• ISSN
• 0302-9743
• Extra Information
• Theory and Applications of Models of Computation
  7th Annual Conference, TAMC 2010
  Lecture Notes in Computer Science, 6108
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2010 Springer-Verlag
• Related URLs
• • http://kam.mff.cuni.cz/~tamc/(Other)
• Depositing User
• Nicholas Korpelainen