Constant amortized time enumeration of Eulerian trails

DOI10.1016/j.tcs.2022.04.048OpenAlexW3121322823MaRDI QIDQ2672609

Kunihiro Wasa, Kazuhiro Kurita

Publication date: 13 June 2022

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

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)

Related Items

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

Cites Work

• Unnamed Item
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Synchronizing finite automata on Eulerian digraphs.
• Efficient enumeration of bipartite subgraphs in graphs
• A note on finding the bridges of a graph
• Reverse search for enumeration
• Beyond the BEST theorem: fast assessment of Eulerian trails
• Amortized $\tilde{O}(|V|)$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• Finding Double Euler Trails of Planar Graphs in Linear Time
• Constant Time Enumeration by Amortization
• A New Algorithm for Generating All the Maximal Independent Sets
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Optimal Listing of Cycles and st-Paths in Undirected Graphs