A beam search for the shortest common supersequence problem guided by an approximate expected length calculation

DOI10.1007/978-3-031-04148-8_9zbMath1499.68426OpenAlexW4226340682MaRDI QIDQ2163793

Markus Kirchweger, Marc Huber, Günther R. Raidl, Jonas Mayerhofer

Publication date: 11 August 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-04148-8_9

zbMATH Keywords

beam searchshortest common supersequence problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• The shortest common supersequence problem over binary alphabet is NP- complete
• Theory and algorithms for plan merging
• Anytime algorithms for the longest common palindromic subsequence problem
• The Complexity of Some Problems on Subsequences and Supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Probabilistic Beam Search for the Longest Common Subsequence Problem

This page was built for publication: A beam search for the shortest common supersequence problem guided by an approximate expected length calculation