RAIRO - Operations Research (RAIRO: RO)

DOI: 10.1051/ro:1999119

RAIRO Rech. Opér. (vol. 33, n $^\circ$ 4, 1999, pp. 421-437)

On the parallel complexity of the alternating Hamiltonian cycle problem

E. Bampis,¹ Y. Manoussakis² and I. Milis²

¹LaMI, Université d'Evry-Val-d'Essonne, 91025 Evry Cedex, France.
²L.R.I., bâtiment 490, Université de Paris-Sud, 91405 Orsay Cedex, France.

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, even 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(\sqrt {n} )$ .