An Optimal O ( nm ) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph

DOI10.1145/3341731zbMath1454.92021OpenAlexW2965565043MaRDI QIDQ4973044

Paul Medvedev, Nidia Obscura Acosta, Romeo Rizzi, Massimo Cairo, Alexandru I. Tomescu

Publication date: 2 December 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3341731

zbMATH Keywords

graph algorithmgenome assemblystrong bridgeedge-covering walksafe and complete algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Genetics and epigenetics (92D10) Computational methods for problems pertaining to biology (92-08)

Related Items (4)

Safety and completeness in flow decompositions for RNA assembly ⋮ Simplicity in Eulerian circuits: uniqueness and safety ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Safety in \(s\)-\(t\) paths, trails and walks

This page was built for publication: An Optimal O ( nm ) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph