On the parallel complexity of the alternating Hamiltonian cycle problem

Bampis, E., Manoussakis, Y., and Milis, I.. "On the parallel complexity of the alternating Hamiltonian cycle problem." RAIRO - Operations Research 33.4 (2010): 421-437. <http://eudml.org/doc/197799>.

@article{Bampis2010,
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\} )$. },
author = {Bampis, E., Manoussakis, Y., Milis, I.},
journal = {RAIRO - Operations Research},
keywords = {; graph with colored edges; Hamiltonian cycle},
language = {eng},
month = {3},
number = {4},
pages = {421-437},
publisher = {EDP Sciences},
title = {On the parallel complexity of the alternating Hamiltonian cycle problem},
url = {http://eudml.org/doc/197799},
volume = {33},
year = {2010},
}

TY - JOUR
AU - Bampis, E.
AU - Manoussakis, Y.
AU - Milis, I.
TI - On the parallel complexity of the alternating Hamiltonian cycle problem
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 4
SP - 421
EP - 437
AB - 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} )$.
LA - eng
KW - ; graph with colored edges; Hamiltonian cycle
UR - http://eudml.org/doc/197799
ER -