An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs

Details An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs

2006-10-26

arxiv.org/abs/math/0610779v1

Mathematics

Combinatorics

2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An effective algorithm for the enumeration of edge colorings and Hamiltonian cycles in cubic graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-114570