On the parallel complexity of the alternating Hamiltonian cycle problem

On the parallel complexity of the alternating Hamiltonian cycle problem

0.00 Avg rating0 Votes
Article ID: iaor20052745
Country: France
Volume: 33
Issue: 4
Start Page Number: 421
End Page Number: 437
Publication Date: Oct 1999
Journal: RAIRO Operations Research
Authors: , ,
Abstract:

Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, ever for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows us to derive a parallel algorithm for the problem. Our parallel solution uses a perfect matching algorithm putting the alternating Hamiltonian cycle problem to the RNC class. In addition, a sequential version of our parallel algorithm improves the computation time of the fastest known sequential algorithm for the alternating Hamiltonian cycle problem by a factor of O(√n).

Reviews

Required fields are marked *. Your email address will not be published.