# On the parallel complexity of the alternating Hamiltonian cycle problem

E. Bampis; Y. Manoussakis; I. Milis

RAIRO - Operations Research (2010)

- Volume: 33, Issue: 4, page 421-437
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topBampis, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.