Alternating paths in edge-colored complete graphs

DOI10.1016/0166-218X(94)00091-QzbMath0819.05039MaRDI QIDQ1842658

Yannis Manoussakis

Publication date: 4 May 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

algorithmNP-completenesscomplete graphedge-colored graphalternating pathedge-colorings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items

Packing problems in edge-colored graphs ⋮ On the tractability of shortest path problems in weighted edge-coloured graphs ⋮ Paths and trails in edge-colored graphs ⋮ Alternating cycles and paths in edge-coloured multigraphs: A survey ⋮ Alternating kernels ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ The price of optimum: complexity and approximation for a matching game ⋮ Links in edge-colored graphs ⋮ Paths and Trails in Edge-Colored Graphs ⋮ On supereulerian 2-edge-coloured graphs ⋮ Maximum colored trees in edge-colored graphs ⋮ On s-t paths and trails in edge-colored graphs ⋮ Paths and trails in edge-colored weighted graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Matching theory
• The directed subgraph homeomorphism problem
• Alternating Hamiltonian cycles
• Packing problems in edge-colored graphs
• Graphs with Hamiltonian cycles having adjacent lines different colours
• The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle
• Graph minors. XIII: The disjoint paths problem
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results