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

co-linear chaininglongest common subsequencepan-genomicspattern matching

Mathematics Subject Classification ID

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

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

(9)

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

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)