Chaining of maximal exact matches in graphs

DOI10.1007/978-3-031-43980-3_29MaRDI QIDQ6545445

Veli Mäkinen, Nicola Rizzo, Manuel O. Cáceres

Publication date: 29 May 2024

zbMATH Keywords

longest common subsequencesparse dynamic programmingsequence-to-graph alignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Solving string problems on graphs using the labeled direct product
• A linear-time parameterized algorithm for computing the width of a DAG
• Sparse Dynamic Programming on DAGs with Small Width
• Linear-time String Indexing and Analysis in Small Space
• Sequence to graph alignment using gap-sensitive co-linear chaining
• On the Complexity of String Matching for Graphs
• Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time
• Parameterized algorithms for string matching to DAGs: funnels and beyond

This page was built for publication: Chaining of maximal exact matches in graphs