Anytime algorithms for the longest common palindromic subsequence problem

DOI10.1016/j.cor.2019.104827zbMath1458.68289OpenAlexW2980782301WikidataQ127023015 ScholiaQ127023015MaRDI QIDQ2337390

Günther R. Raidl, Marko Djukanovic, Christian Blum

Publication date: 19 November 2019

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2019.104827

zbMATH Keywords

beam searchhybrid algorithmsanytime algorithmsA* searchlongest common palindromic subsequence problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Approximation methods and heuristics in mathematical programming (90C59) Algorithms on strings (68W32)

Related Items (1)

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

Uses Software

• irace
• scmamp

Cites Work

• Computing a longest common subsequence for a set of strings
• Beam search for the longest common subsequence problem
• A fast algorithm for computing a longest common increasing subsequence
• A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem
• The longest common subsequence problem for arc-annotated sequences
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• A large neighborhood search heuristic for the longest common subsequence problem
• An improved algorithm for the longest common subsequence problem
• Anytime pack search
• Palindromic subsequence automata and longest common palindromic subsequence
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Expected length of the longest common subsequence for large alphabets
• Constrained LCS: Hardness and Approximation
• Longest common subsequences of two random sequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms on Strings, Trees and Sequences
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Computing a Longest Common Palindromic Subsequence
• Repetition-free longest common subsequence
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Anytime algorithms for the longest common palindromic subsequence problem