Fast distance multiplication of unit-Monge matrices

MaRDI QIDQ5417707zbMATH OpenFDO

Authors Alexander Tiskin

Publication date 22 May 2014

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Numerical linear algebra (65F99) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Fast distance multiplication of unit-Monge matrices
• Monge properties of sequence alignment
• Spanning trees and shortest paths in Monge graphs
• Monge matrices make maximization manageable
• An \(O(n^{2}\)) algorithm for maximum cycle mean of Monge matrices in max-algebra.

Cited in

(11)

• Unified compression-based acceleration of edit-distance computation
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• Four-point conditions for the TSP: the complete complexity classification
• Fast distance multiplication of unit-Monge matrices
• Efficient all path score computations on grid graphs
• A maximum weight clique algorithm for dense circle graphs with many shared endpoints
• Towards approximate matching in compressed strings: local subsequence recognition
• A fast algorithm for multiplying min-sum permutations
• Monge properties of sequence alignment
• On totally positive matrices and geometric incidences
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs

This page was built for publication: Fast distance multiplication of unit-Monge matrices

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