A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem

DOI10.1007/978-3-030-78230-6_5MaRDI QIDQ2117202zbMATH OpenOpenAlexFDO

Authors Matthias Horn, Günther R. Raidl

Publication date 21 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-78230-6_5

zbMATH Keywords

longest common subsequence problemmulti-valued decision diagramA\textsuperscript{*} search

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• On the use of decision diagrams for finding repetition-free longest common subsequences
• Algorithms for Computing Variants of the Longest Common Subsequence Problem
• Publication:4862293
• On solving a generalized constrained longest common subsequence problem
• A local search framework for compiling relaxed decision diagrams
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• On the generalized constrained longest common subsequence problems
• The longest common subsequence problem -- a finite automata approach
• On the parameterized complexity of the repetition free longest common subsequence problem
• A branch-and-cut approach to the repetition-free longest common subsequence problem

Cites work

• A large neighborhood search heuristic for the longest common subsequence problem
• Algorithms on Strings, Trees and Sequences
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Beam search for the longest common subsequence problem
• Decision diagrams for optimization
• Discrete optimization with decision diagrams
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• Hybrid optimization methods for time-dependent sequencing problems
• Multivalued decision diagrams for sequencing problems
• Optimization Bounds from Binary Decision Diagrams
• Probabilistic Beam Search for the Longest Common Subsequence Problem
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• The Complexity of Some Problems on Subsequences and Supersequences
• \(\mathrm{A}^*\)-based construction of decision diagrams for a prize-collecting scheduling problem

Cited in

(1)

• Decision Diagrams for Discrete Optimization: A Survey of Recent Advances

This page was built for publication: A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem

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