{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:24Z","timestamp":1759638084399},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":4394,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1996,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1017\/s0963548300002054","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:13:14Z","timestamp":1221217994000},"page":"297-306","source":"Crossref","is-referenced-by-count":13,"title":["Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP"],"prefix":"10.1017","volume":"5","author":[{"given":"Rachid","family":"Saad","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300002054_ref002","unstructured":"[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."},{"key":"S0963548300002054_ref014","volume-title":"Handbook of Theoretical Computer Science","volume":"A","author":"Leeuwen","year":"1990"},{"key":"S0963548300002054_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122681"},{"key":"S0963548300002054_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"S0963548300002054_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90053-8"},{"key":"S0963548300002054_ref001","volume-title":"Theory of Graphs (Proc. Colloq. Tihany)","author":"Bankfalvi","year":"1968"},{"key":"S0963548300002054_ref013","unstructured":"[13] Poljak S. Private communication."},{"key":"S0963548300002054_ref010","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050204"},{"key":"S0963548300002054_ref012","unstructured":"[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."},{"key":"S0963548300002054_ref003","article-title":"Alternating Cycles through fixed vertices in edge colored graphs","author":"Benkouar","journal-title":"J. Combinatorial Maths and Combinatorial Comput."},{"key":"S0963548300002054_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/BF02756791"},{"key":"S0963548300002054_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(82)90029-6"},{"key":"S0963548300002054_ref007","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-12245"},{"key":"S0963548300002054_ref008","unstructured":"[8] Gutin G. Private communication."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300002054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T20:42:39Z","timestamp":1557693759000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300002054\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["S0963548300002054"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300002054","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}