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

DOI10.1007/S10878-020-00644-7MaRDI QIDQ830935zbMATH OpenOpenAlexFDO

Authors Ruonan Li, Zhiwei Guo, Hajo Broersma, Shenggui Zhang

Publication date 10 May 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

compatible spanning circuitedge-colored graphNP-complete problempolynomial-time algorithm

Mathematics Subject Classification ID

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

Recommendations

• Compatible spanning circuits in edge-colored graphs
• Almost Eulerian compatible spanning circuits in edge-colored graphs
• Eulerian Circuits with No Monochromatic Transitions in Edge-colored Digraphs
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
• Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three

Cites work

• A property of the colored complete graph
• Alternating Hamiltonian cycles
• Compatible spanning circuits in edge-colored graphs
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Graph theory
• Graphs with cycles having adjacent lines different colors
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
• scientific article; zbMATH DE number 15867 (Why is no real title available?)
• scientific article; zbMATH DE number 1067836 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 3249675 (Why is no real title available?)
• Properly colored paths and cycles
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• The orderly colored longest path problem -- a survey of applications and new algorithms

Cited in

(4)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q830935)