aalto1 untyped-item.component.html
An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph
Loading...
Files
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
1-17
Series
ACM Transactions on Algorithms, Volume 15, issue 4
Abstract
In this article, we consider the following problem. Given a directed graph G, output all walks of G that are sub-walks of all closed edge-covering walks of G. This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig. Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Ω(nm). We implement this algorithm and show that it is 9--12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).
Description
Keywords
Other note
Citation
Cairo, M, Medvedev, P, Acosta, N O, Rizzi, R & Tomescu, A I 2019, ' An optimal O(nm) algorithm for enumerating all walks common to all closed edge-covering walks of a graph ', ACM Transactions on Algorithms, vol. 15, no. 4, 48, pp. 1-17 . https://doi.org/10.1145/3341731