Constant amortized time enumeration of Eulerian trails

DOI10.1016/J.TCS.2022.04.048MaRDI QIDQ2672609zbMATH OpenOpenAlexFDO

Authors Kazuhiro Kurita, Kunihiro Wasa

Publication date 13 June 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2101.10473

zbMATH Keywords

constant amortized timeenumeration algorithmEulerian trailoutput-sensitive algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Linear amortized time enumeration algorithms for compatible Euler trails in edge-colored graphs
• Enumerating Eulerian trails via Hamiltonian path enumeration
• Computing Eulerian trails
• An algorithm for an Eulerian trail traversing specified edges in given order
• Exact counting of Euler tours for generalized series-parallel graphs

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A note on finding the bridges of a graph
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Beyond the BEST theorem: fast assessment of Eulerian trails
• Constant time enumeration by amortization
• Efficient enumeration of bipartite subgraphs in graphs
• Finding Double Euler Trails of Planar Graphs in Linear Time
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• Optimal listing of cycles and st-paths in undirected graphs
• Reverse search for enumeration
• Synchronizing finite automata on Eulerian digraphs.
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(1)

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

This page was built for publication: Constant amortized time enumeration of Eulerian trails

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