Constant amortized time enumeration of Eulerian trails

DOI10.1016/J.TCS.2022.04.048OpenAlexW3121322823MaRDI QIDQ2672609FDOQ2672609

Authors: Kazuhiro Kurita, Kunihiro Wasa 

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

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

zbMATH Keywords

constant amortized timeenumeration algorithmEulerian trailoutput-sensitive algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)