2025-06-10
Shortest undirected paths in de Bruijn graphs
Publication
Publication
Computing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V, E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2 − 2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from O(k|V |2) to O(k|V |log d) time, where d is the number of weakly connected components of graph G.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.4230/LIPIcs.CPM.2025.12 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| Pan-genome Graph Algorithms and Data Integration , Algorithms for PAngenome Computational Analysis | |
| 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025 | |
| , | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Zuba, W., Lachish, O., & Pissis, S. (2025). Shortest undirected paths in de Bruijn graphs. In Proceedings of the 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025 (pp. 12:1–12:13). doi:10.4230/LIPIcs.CPM.2025.12 |
|
