A fast algorithm for multiplying min-sum permutations

DOI10.1016/j.dam.2011.06.022zbMath1236.05007OpenAlexW2078611081MaRDI QIDQ411869

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)

Related Items (5)

A substring-substring LCS data structure ⋮ A faster reduction of the dynamic time warping distance to the longest increasing subsequence length ⋮ An almost quadratic time algorithm for sparse spliced alignment ⋮ Unnamed Item ⋮ A data structure for substring-substring LCS length queries

Cites Work

• Semi-local string comparison: algorithmic techniques and applications
• Semi-local longest common subsequences in subquadratic time
• A linear-time algorithm for a special case of disjoint set union
• On the Common Substring Alignment Problem
• Unnamed Item
• Unnamed Item

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