A fast algorithm for multiplying min-sum permutations

DOI10.1016/J.DAM.2011.06.022MaRDI QIDQ411869zbMATH OpenOpenAlexFDO

Authors Yoshifumi Sakai

Publication date 30 April 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.06.022

zbMATH Keywords

algorithmsmatrix multiplicationsemi-local string comparison

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Recommendations

• Fast algorithms to enumerate all common intervals of two permutations
• Fast algorithms for the dominating set problem on permutation graphs
• Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• scientific article; zbMATH DE number 2038722

Cites work

• scientific article; zbMATH DE number 5158495 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Fast distance multiplication of unit-Monge matrices
• On the common substring alignment problem
• Semi-local longest common subsequences in subquadratic time
• Semi-local string comparison: algorithmic techniques and applications

Cited in

(6)

• A substring-substring LCS data structure
• An almost quadratic time algorithm for sparse spliced alignment
• A data structure for substring-substring LCS length queries
• Applying fast simulation to find the number of good permutations
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• scientific article; zbMATH DE number 7765364 (Why is no real title available?)

This page was built for publication: A fast algorithm for multiplying min-sum permutations

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