2026-07-22T06:27:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23106 2025-10-02T12:37:42Z ddc:004 open_access

Shortest Undirected Paths in de Bruijn Graphs Zuba, Wiktor Lachish, Oded Pissis, Solon P. string algorithm graph algorithm de Bruijn graph Eulerian graph 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 𝒪(k|V|²) to 𝒪(k|V|log d) time, where d is the number of weakly connected components of graph G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wiktor Zuba and Oded Lachish and Solon P. Pissis 2025 Is Part Of LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2025.12 urn:nbn:de:0030-drops-231060 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode