On the parallel complexity of the alternating hamiltonian cycle problem

 Access to full text

 Full (PDF)

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