A fast algorithm for multiplying min-sum permutations

The present article considers the problem for determining, for given two permutations over indices from 11 to nn, the permutation whose distribution matrix is identical to the min-sum product of the distribution matrices of the given permutations. This problem has several applications in computing the similarity between strings. The fastest known algorithm to date for solving this problem executes in O(n1.5)O(n1.5) time, or very recently, in O(nlogn)O(nlogn) time. The present article independently proposes another O(nlogn)O(nlogn)-time algorithm for the same problem, which can also be used to partially solve the problem efficiently with respect to time in the sense that, for given indices gg and ii with 1≤g

► We consider min-sum multiplication of the distribution matrices of permutations. ► A new algorithm that solves the min-sum multiplication problem is proposed. ► The execution time is O(nlogn)O(nlogn), where nn is the size of the permutations. ► The proposed algorithm performs based on a simple top-down approach. ► The algorithm can also be used to partially solve the problem efficiently.