Parameterized algorithms in smooth 4-regular Hamiltonian graphs

DOI10.1007/S11786-007-0031-5MaRDI QIDQ943003zbMATH OpenOpenAlexFDO

Authors Egbert Mujuni

Publication date 8 September 2008

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11786-007-0031-5

zbMATH Keywords

algorithmgraph coloringindependent setparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
• A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Solution to an open problem on 4-ordered Hamiltonian graphs
• Hamiltonicity in graphs with few \(P_ 4\)'s
• Hamiltonicity of 4-connected graphs
• Exact algorithms for the Hamiltonian cycle problem in planar graphs

Cited in

(2)

• 3-colorability of 4-regular hamiltonian graphs
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs

This page was built for publication: Parameterized algorithms in smooth 4-regular Hamiltonian graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q943003)