Volume 33, Number 4, October-December 1999
|421 - 437
|15 August 2002
On the parallel complexity of the alternating Hamiltonian cycle problem
LaMI, Université d'Evry-Val-d'Essonne,
91025 Evry Cedex, France.
2 L.R.I., bâtiment 490, Université de Paris-Sud, 91405 Orsay Cedex, France.
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 .
© EDP Sciences, 1999
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.