Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended

DOI10.1007/978-3-319-89929-9_7MaRDI QIDQ5881345zbMATH OpenOpenAlexFDO

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

Publication date 9 March 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.08754

Mathematics Subject Classification ID

Applications of graph theory (05C90) Protein sequences, DNA sequences (92D20) Dynamic programming (90C39)

Recommendations

• Sparse dynamic programming on DAGs with small width
• Covering pairs in directed acyclic graphs
• Co-linear chaining with overlaps and gap costs
• Multiple genome alignment: chaining algorithms revisited
• A Path Cover Technique for LCAs in Dags

Cites work

• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 910858 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Improved approximate pattern matching on hypertext
• Indexing variation graphs
• Linear time construction of compressed text indices in compact space
• Max flows in \(O(nm)\) time, or better
• Network flows. Theory, algorithms, and applications.
• Nonlinear dynamic analysis of the viscoelastic string with a harmonically varying transport speed
• Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Pattern Matching in Hypertext
• Reachability and Distance Queries via 2-Hop Labels
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• Sparse dynamic programming I
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• Versatile succinct representations of the bidirectional Burrows-Wheeler transform

Cited in

(8)

• Algorithms and bounds for drawing directed graphs
• A new framework for hierarchical drawings
• Covering pairs in directed acyclic graphs
• Sequence to graph alignment using gap-sensitive co-linear chaining
• Sparse dynamic programming on DAGs with small width
• Co-linear chaining with overlaps and gap costs
• Co-linear chaining on pangenome graphs
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended

This page was built for publication: Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended

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