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

DOI10.1017/S0963548300002054zbMath0865.05054OpenAlexW2085072166MaRDI QIDQ4715273

Rachid Saad

Publication date: 29 June 1997

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548300002054

zbMATH Keywords

cyclecomplete graphedge colouringalternating cycleexact matchingrandomly polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Paths and trails in edge-colored graphs ⋮ Alternating cycles and paths in edge-coloured multigraphs: A survey ⋮ Proper‐walk connection number of graphs ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ Odd properly colored cycles in edge-colored graphs ⋮ Unnamed Item ⋮ A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs ⋮ Paths and Trails in Edge-Colored Graphs ⋮ On supereulerian 2-edge-coloured graphs ⋮ Maximum colored trees in edge-colored graphs ⋮ Properly Coloured Cycles and Paths: Results and Open Problems ⋮ Characterization of edge-colored complete graphs with properly colored Hamilton paths ⋮ Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs ⋮ On connectivities of edge-colored graphs

Cites Work

• Unnamed Item
• Constructing a perfect matching is in random NC
• Cycles in bipartite tournaments
• Alternating Hamiltonian cycles
• Symmetric designs and geometroids
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Hamilton circuits with many colours in properly edge-coloured complete graphs.

This page was built for publication: Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP