Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-27T10:09:45.508Z Has data issue: false hasContentIssue false
  • English
  • Français

Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP

Published online by Cambridge University Press:  12 September 2008

Rachid Saad
Rachid Saad
Affiliation:
Cité Ibn Khaldun, Bât 68 A2, Boumerdes, Algeria
Get access Rights & Permissions [Opens in a new window]

Abstract

Jackson [10] gave a polynomial sufficient condition for a bipartite tournament to contain a cycle of a given length. The question arises as to whether deciding on the maximum length of a cycle in a bipartite tournament is polynomial. The problem was considered by Manoussakis [12] in the slightly more general setting of 2-edge coloured complete graphs: is it polynomial to find a longest alternating cycle in such coloured graphs? In this paper, strong evidence is given that such an algorithm exists. In fact, using a reduction to the well known exact matching problem, we prove that the problem is random polynomial.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 3 , September 1996 , pp. 297 - 306
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bankfalvi, M. and Bankfalvi, Z. (1968) Alternating Hamiltonian circuit in two-colored complete graphs. Theory of Graphs (Proc. Colloq. Tihany). Academic Press.Google Scholar
[2]Benkouar, A., Manoussakis, Y., Paschos, V. and Saad, R. On the complexity of some Hamiltonian and Eulerian problems in edge coloured complete graphs. Submitted.Google Scholar
[3]Benkouar, A., Manoussakis, Y. and Saad, R.Alternating Cycles through fixed vertices in edge colored graphs. J. Combinatorial Maths and Combinatorial Comput. To appear.Google Scholar
[4]Beineke, L. and Little, C. (1982) Cycles in bipartite tournaments. J. Comb. Theory (B) 32 140–145.Google Scholar
[5]Bollobás, B. and Erdős, P. (1976) Alternating Hamiltonian Cycles. Israel J. Math. 23 126–131.CrossRefGoogle Scholar
[6]Chen, C. C. and Daykin, D. E. (1976) Graphs with Hamiltonian cycles having adjacent lines different colors. J. Combinatorial Theory (B) 21 135–139.CrossRefGoogle Scholar
[7]Dovling Andersen, L (1989) Long alternating cycles in properly edge colored complete graphs. Math. Scandinavica 5–14.CrossRefGoogle Scholar
[8]Gutin, G. Private communication.Google Scholar
[9]Häggkvist, R. and Manoussakis, Y. (1989) Cycles and paths in bipartite tournaments with spanning configurations. Combinatorica 9(1) 51–56.Google Scholar
[10]Jackson, B. (1981) Long paths and cycles in oriented graphs. J. Graph Theory.CrossRefGoogle Scholar
[11]Karp, R. M., Upfal, E. and Wigderson, A. (1985) Constructing a perfect matching is in random NC. Combinatorica 6 35–48.CrossRefGoogle Scholar
[12]Manoussakis, Y. (1990) On the complexity of finding alternating paths in edge coloured complete graphs. Technical Report NO 573, University of Paris 11. Submitted.Google Scholar
[13]Poljak, S. Private communication.Google Scholar
[14]Leeuwen, Van (ed.) (1990) Handbook of Theoretical Computer Science, Vol. A. Elsevier.Google Scholar