Sparse Dynamic Programming on DAGs with Small Width

DOI10.1145/3301312zbMath1454.68112OpenAlexW2913934544WikidataQ128440355 ScholiaQ128440355MaRDI QIDQ4972674

Topi Paavilainen, Veli Mäkinen, Alexandru I. Tomescu, Rayan Chikhi, Travis Gagie, Anna Kuosmanen

Publication date: 25 November 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10138/303127

zbMATH Keywords

pattern matchinglongest common subsequenceco-linear chainingpan-genomics

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Genetics and epigenetics (92D10) Directed graphs (digraphs), tournaments (05C20) Algorithms on strings (68W32)

Related Items (4)

Co-linear chaining with overlaps and gap costs ⋮ A linear-time parameterized algorithm for computing the width of a DAG ⋮ Sequence to graph alignment using gap-sensitive co-linear chaining ⋮ Elastic founder graphs improved and enhanced

This page was built for publication: Sparse Dynamic Programming on DAGs with Small Width