An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs
From MaRDI portal
Publication:6478110
arXivmath/0610779MaRDI QIDQ6478110FDOQ6478110
Authors: Vladimir Ejov, N. Pugacheva, Serguei Rossomakhine, Peter Zograf 
Publication date: 26 October 2006
Abstract: We propose an effective algorithm that enumerates (and actually finds) all 3-edge colorings and Hamiltonian cycles in a cubic graph. The idea is to make a preliminary run that separates the vertices into two types: ``rigid (such that the edges incident to them admit a unique coloring) and ``soft ones (such that the edges incident to them admit two distinct colorings), and then to perform the coloring. The computational complexity of this algorithm is on a par with (or even below) the fastest known algorithms that find a single 3-edge coloring or a Hamiltonian cycle for a cubic graph.
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
This page was built for publication: An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478110)
