Polynomial-time equivalences and refined algorithms for longest common subsequence variants

DOI10.1016/J.DAM.2024.04.006MaRDI QIDQ6546417

Yuichi Asahiro, Guohui Lin, Hirotaka Ono, Eiji Miyano, Tadatoshi Utashima, Jesper Jansson

Publication date: 29 May 2024

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

zbMATH Keywords

dynamic programmingapproximation algorithmexact algorithmlongest common subsequencemultiset-restrictedone-side-filledrepetition-boundedtwo-side-filled

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Heuristic algorithms for the min-max edge 2-coloring problem
• Exact algorithms for the repetition-bounded longest common subsequence problem
• Comparing incomplete sequences via longest common subsequence
• An Extension of the String-to-String Correction Problem
• A linear space algorithm for computing maximal common subsequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• The longest filled common subsequence problem
• Repetition-free longest common subsequence
• Better heuristic algorithms for the repetition free LCS and other variants
• Polynomial-time equivalences and refined algorithms for longest common subsequence variants

This page was built for publication: Polynomial-time equivalences and refined algorithms for longest common subsequence variants

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