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

DOI10.1017/S0963548300002054zbMath0865.05054MaRDI QIDQ4715273

Rachid Saad

Publication date: 29 June 1997

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

zbMATH Keywords

cycle; complete graph; edge colouring; alternating cycle; exact matching; randomly polynomial

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Paths and Trails in Edge-Colored Graphs, Alternating cycles and paths in edge-coloured multigraphs: A survey, Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs, Paths and trails in edge-colored graphs, Characterization of edge-colored complete graphs with properly colored Hamilton paths, Properly Coloured Cycles and Paths: Results and Open Problems

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.