Some algorithmic results for finding compatible spanning circuits in edge-colored graphs

DOI10.1007/s10878-020-00644-7zbMath1462.05140OpenAlexW3083134246MaRDI QIDQ830935

Ruonan Li, Sheng Gui Zhang, Zhi-Wei Guo, Hajo J. Broersma

Publication date: 10 May 2021

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00644-7

zbMATH Keywords

polynomial-time algorithmedge-colored graphNP-complete problemcompatible spanning circuit

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (2)

Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs ⋮ Compatible spanning circuits and forbidden induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Properly colored paths and cycles
• Graphs with cycles having adjacent lines different colors
• Alternating Hamiltonian cycles
• A property of the colored complete graph
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Graphs with Hamiltonian cycles having adjacent lines different colours
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Compatible spanning circuits in edge-colored graphs
• The Orderly Colored Longest Path Problem – a survey of applications and new algorithms
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results

This page was built for publication: Some algorithmic results for finding compatible spanning circuits in edge-colored graphs