Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

DOI10.1007/S10878-023-01005-WMaRDI QIDQ2687939zbMATH OpenOpenAlexFDO

Authors Yuhang Bai, Yandong Bai, Zhiwei Guo, Shenggui Zhang

Publication date 7 March 2023

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

Full work available at URL https://doi.org/10.1007/s10878-023-01005-w

zbMATH Keywords

compatible Euler trailedge-colored graphenumeration algorithmlinear amortized time

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Mathematical programming (90Cxx)

Recommendations

• Some algorithmic results for finding compatible spanning circuits in edge-colored graphs
• Eulerian Circuits with No Monochromatic Transitions in Edge-colored Digraphs
• On \(s\)--\(t\) paths and trails in edge-colored graphs
• Eulerian Circuits with No Monochromatic Transitions in Edge-Colored Digraphs with all Vertices of Outdegree Three
• scientific article; zbMATH DE number 1947434

Cites work

• A note on finding the bridges of a graph
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Beyond the BEST theorem: fast assessment of Eulerian trails
• Compatible Euler tours for transition systems in Eulerian graphs
• Constant amortized time enumeration of Eulerian trails
• Constant time enumeration by amortization
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Graph theory
• 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 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 3249675 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• On the maximum number of pairwise compatible euler cycles
• Some algorithmic results for finding compatible spanning circuits in edge-colored graphs

Cited in

(6)

• Some conditions for the existence of Euler H-trails
• Constant amortized time enumeration of Eulerian trails
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• scientific article; zbMATH DE number 1947434 (Why is no real title available?)
• Enumerating Eulerian trails via Hamiltonian path enumeration
• Euler dynamic H -trails in edge-colored graphs

This page was built for publication: Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs

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