On the parallel complexity of the alternating hamiltonian cycle problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 4, pp. 421-437. 
@article{RO_1999__33_4_421_0,
     author = {Bampis, E. and Manoussakis, Y. and Milis, I.},
     title = {On the parallel complexity of the alternating hamiltonian cycle problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {421--437},
     publisher = {EDP-Sciences},
     volume = {33},
     number = {4},
     year = {1999},
     mrnumber = {1735446},
     zbl = {0952.68115},
     language = {en},
     url = {http://archive.numdam.org/item/RO_1999__33_4_421_0/}
}
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 - Recherche Opérationnelle
PY  - 1999
SP  - 421
EP  - 437
VL  - 33
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_1999__33_4_421_0/
LA  - en
ID  - RO_1999__33_4_421_0
ER  - 
%0 Journal Article
%A Bampis, E.
%A Manoussakis, Y.
%A Milis, I.
%T On the parallel complexity of the alternating hamiltonian cycle problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 1999
%P 421-437
%V 33
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_1999__33_4_421_0/
%G en
%F RO_1999__33_4_421_0
Bampis, E.; Manoussakis, Y.; Milis, I. On the parallel complexity of the alternating hamiltonian cycle problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 33 (1999) no. 4, pp. 421-437. http://archive.numdam.org/item/RO_1999__33_4_421_0/

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. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

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. | MR | Zbl

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. | Numdam | MR | Zbl

6. B. Bollobás and P. Erdös, Alternating Hamiltonian cycles, Israel J. Math., 1976, 23, p. 126-131. | MR | Zbl

7. R. Brent, The parallel evaluation of general arithmetic expressions, J. ACM 1974, 21, p. 201-206. | MR | Zbl

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. | MR | Zbl

9. D. Cartwright and F. Harary, Structural balance: A generalization of Heider's theory, Psychological Rev., 1956, 73, p. 277-293.

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. 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. | MR | Zbl

12. D. Dornjger, Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 1994, 50, p. 159-168. | MR | Zbl

13. D. Dorniger and W. Timischl, Geometrical constraints on Bennetfs predictions of chromosome order, Heredity, 1987, 58, p. 321-325.

14. J. Edmonds, Paths, trees and flowers, Canad. J. Math., 1965, 17, p. 449-467. | MR | Zbl

15. T. C. Hu and Y. S. Kuo, Graph folding andprogrammable logical arrays, Networks, 1987, 17, p. 19-37. | MR | Zbl

16. R. Häggvist and Y. Manoussakis, Cycles and paths in bipartite tournaments with spanning configurations, Combinatorica, 1989, 9, p. 33-38. | MR | Zbl

17. A. Israeli and Y. Shiloach, An improved parallel algorithm for maximal matching, Inform. Process. Lett., 1986, 22, p. 57-60. | MR | Zbl

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. K. Mulmuley, U. V. Vazirani and V. B. Vazirani, Matching is as easy as matrix inversion, Combinatorica, 1987, 7, p. 105-113. | MR | Zbl

20. P. A. Pevzner, DNA Physical mapping and alternating Eulerian cycles in colored graphs, Algorithmica, 1995, 13, p. 77-105. | MR | Zbl

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. 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. | MR | Zbl