Sparse dynamic programming on DAGs with small width

DOI10.1145/3301312MaRDI QIDQ4972674zbMATH OpenOpenAlexWikidataFDO

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

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

longest common subsequencepattern matchingco-linear chainingpan-genomics

Mathematics Subject Classification ID

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

Recommendations

• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Covering pairs in directed acyclic graphs
• A Path Cover Technique for LCAs in Dags
• scientific article; zbMATH DE number 432798
• Publication:4886031

Cited in

(8)

• Covering pairs in directed acyclic graphs
• Sequence to graph alignment using gap-sensitive co-linear chaining
• Algorithms and complexity for path covers of temporal DAGs
• Elastic founder graphs improved and enhanced
• Co-linear chaining with overlaps and gap costs
• A linear-time parameterized algorithm for computing the width of a DAG
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Chaining of maximal exact matches in graphs

This page was built for publication: Sparse dynamic programming on DAGs with small width

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