Complexity of the hamiltonian cycle in regular graph problem

DOI10.1016/0304-3975(94)90185-6zbMath0809.68091OpenAlexW1977187614MaRDI QIDQ1331931

Christophe Picouleau

Publication date: 20 March 1995

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90185-6

zbMATH Keywords

NP-complete problemhamiltonian cycle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (14)

Global cycle properties of locally isometric graphs ⋮ Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs ⋮ On Hamiltonicity of regular graphs with bounded second neighborhoods ⋮ Shifted de Bruijn Graphs ⋮ Unnamed Item ⋮ Nominal Unification and Matching of Higher Order Expressions with Recursive Let ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Conjecture of TxGraffiti: Independence, domination, and matchings ⋮ On 3-degree 4-chordal graphs ⋮ Hamiltonian properties of locally connected graphs with bounded vertex degree ⋮ Hamilton cycles in sparse locally connected graphs ⋮ Global cycle properties in graphs with large minimum clustering coefficient ⋮ Complexity of some arc-partition problems for digraphs

Cites Work

• The Planar Hamiltonian Circuit Problem is NP-Complete
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of the hamiltonian cycle in regular graph problem