Connecting de Bruijn graphs

DOI10.4230/LIPICS.CPM.2024.6MaRDI QIDQ6891094zbMATH OpenFDO

Authors Giulia Bernardini, Huiping Chen, Inge Li Gørtz, Christoffer Krogh, Grigorios Loukides, Solon P. Pissis, L. Stougie, Michelle Sweering

Publication date 2 December 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2024.6

zbMATH Keywords

de Bruijn graphEulerian graphgraph algorithmstring algorithm

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• A better approximation ratio for the vertex cover problem
• A fast algorithm for Steiner trees
• A linear-time algorithm for finding approximate shortest common superstrings
• All-pairs suffix/prefix in optimal time using Aho-Corasick space
• An efficient algorithm for the all pairs suffix-prefix problem
• An Eulerian path approach to DNA fragment assembly
• An improved algorithm for the all-pairs suffix-prefix problem
• Construction of Aho Corasick automaton in linear time for integer alphabets
• Efficient string matching
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 7695995 (Why is no real title available?)
• Making de Bruijn graphs Eulerian
• On finding minimal length superstrings
• On strings having the same length-\(k\) substrings
• On the power of unique 2-prover 1-round games
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimization, approximation, and complexity classes
• Reducibility among combinatorial problems
• Reverse-safe data structures for text indexing
• Reverse-safe text indexing

Cited in

(2)

• On strings having the same length-k substrings
• Shortest undirected paths in de Bruijn graphs

This page was built for publication: Connecting de Bruijn graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6891094)