On the parallel complexity of the alternating hamiltonian cycle problem

E. Bampis; Y. Manoussakis; I. Milis

RAIRO - Operations Research - Recherche Opérationnelle (1999)

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

How to cite


Bampis, E., Manoussakis, Y., and Milis, I.. "On the parallel complexity of the alternating hamiltonian cycle problem." RAIRO - Operations Research - Recherche Opérationnelle 33.4 (1999): 421-437. <http://eudml.org/doc/105198>.

author = {Bampis, E., Manoussakis, Y., Milis, I.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {graph with colored edges; Hamiltonian cycle},
language = {eng},
number = {4},
pages = {421-437},
publisher = {EDP-Sciences},
title = {On the parallel complexity of the alternating hamiltonian cycle problem},
url = {http://eudml.org/doc/105198},
volume = {33},
year = {1999},

AU - Bampis, E.
AU - Manoussakis, Y.
AU - Milis, I.
TI - On the parallel complexity of the alternating hamiltonian cycle problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 4
SP - 421
EP - 437
LA - eng
KW - graph with colored edges; Hamiltonian cycle
UR - http://eudml.org/doc/105198
ER -


  1. 1. E. BAMPIS, M. EL HADDAD, Y. MANOUSSAKIS and M. SANTHA, A parallel reduction of Hamiltonian cycle to Hamiltonian path in tournaments, J. Algorithms, 1995, 19, p. 432-440. Zbl0836.68051MR1355648
  2. 2. J. BANG-JENSEN, M. EL HADDAD, Y. MANOUSSAKIS and T. M. PRZYTYCKA, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Algorithmica, 1997, 97, p. 67-87. Zbl0864.68049MR1420492
  3. 3. M. BÁNKFALVI and Z. BÁNKFALVI, Alternating Hamiltonian circuit in two-colored complete graphs, Theory of Graphs (Proc. Colloq. Tihany 1968), Academic Press, New York, p. 11-18. Zbl0159.54202MR233731
  4. 4. A. BAR-NOY and J. NAOR, Sorting, minimal feedback sets and Hamiltonian paths in tournaments, SIAM J. Discr. Math., 1990, 3, p. 7-20. Zbl0686.68052MR1033709
  5. 5. A. BENKOUAR, Y. MANOUSSAKIS, V. Th. PASCHOS and R. SAAD, On the complexity of some Hamiltonian and Eulerian problems in edge-colored complete graphs, RAIRO-Oper. Res., 1996, 30, p. 417-438. Zbl0868.90128MR1427450
  6. 6. B. BOLLOBÁS and P. ERDÖS, Alternating Hamiltonian cycles, Israel J. Math., 1976, 23, p. 126-131. Zbl0325.05114MR411999
  7. 7. R. BRENT, The parallel evaluation of general arithmetic expressions, J. ACM 1974, 21, p. 201-206. Zbl0276.68010MR660280
  8. 8. C. C. CHEN and D. E. DAYKIN, Graphs with Hamiltonian cycles having adjacent lines different colors, J. Combin. Theory Ser. B, 1976, 21, P 135-139. Zbl0287.05106MR422070
  9. 9. D. CARTWRIGHT and F. HARARY, Structural balance: A generalization of Heider's theory, Psychological Rev., 1956, 73, p. 277-293. 
  10. 10. R. COLE and U. VISHKIN, Aproximate and exact parallel scheduling with applications to list tree and graph problems, In Proc. 27th FOCS, 1986, p. 478-491. 
  11. 11. D. DORNIGER, On permutations of chromosomes, In Contributions of General Algebra, 5, Verlag Hölder-Pichler-Tempsky, Wien, and Teubner-Verlag, Stuttgart, 1987, p. 95-103. Zbl0643.92012MR930913
  12. 12. D. DORNJGER, Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 1994, 50, p. 159-168. Zbl0823.92010MR1275419
  13. 13. D. DORNIGER and W. TIMISCHL, Geometrical constraints on Bennetfs predictions of chromosome order, Heredity, 1987, 58, p. 321-325. 
  14. 14. J. EDMONDS, Paths, trees and flowers, Canad. J. Math., 1965, 17, p. 449-467. Zbl0132.20903MR177907
  15. 15. T. C. HU and Y. S. KUO, Graph folding andprogrammable logical arrays, Networks, 1987, 17, p. 19-37. Zbl0649.05038MR874286
  16. 16. R. HÄGGVIST and Y. MANOUSSAKIS, Cycles and paths in bipartite tournaments with spanning configurations, Combinatorica, 1989, 9, p. 33-38. Zbl0681.05036MR1010297
  17. 17. A. ISRAELI and Y. SHILOACH, An improved parallel algorithm for maximal matching, Inform. Process. Lett., 1986, 22, p. 57-60. Zbl0588.68035MR827651
  18. 18. S. MICALI and V. V. VAZIRANI, An O(|V|1/2|E|) algorithm for finding maximum matchings in general graphs, In Proc. 21th FOCS, 1980, p. 17-23. 
  19. 19. K. MULMULEY, U. V. VAZIRANI and V. B. VAZIRANI, Matching is as easy as matrix inversion, Combinatorica, 1987, 7, p. 105-113. Zbl0632.68041MR905157
  20. 20. P. A. PEVZNER, DNA Physical mapping and alternating Eulerian cycles in colored graphs, Algorithmica, 1995, 13, p. 77-105. Zbl0840.92011MR1304310
  21. 21. R. SAAD, Finding a longest alternating Hamiltonian cycle in an edge colored complete graph is not hard, Rapport de Recherche No. 691, Laboratoire de Recherche en Informatique, Université de Paris-Sud XI, Sep. 1991, to appear in Combinatorics, Probability and Computing. 
  22. 22. V. V. VAZIRANI, A theory of alternating paths and blossoms for proving correctness of the O(VE) general graph maximum matching algorithm, Combinatorica, 1994, 14, p. 71-109. Zbl0806.05058MR1273202

NotesEmbed ?


You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.