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

DOI10.1007/978-3-319-89929-9_7OpenAlexW2787131599MaRDI QIDQ5881345FDOQ5881345

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)