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

DOI10.1007/978-3-030-78230-6_5OpenAlexW3172429850MaRDI QIDQ2117202FDOQ2117202

Günther R. Raidl, Matthias Horn

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)

Cites Work

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

Cited In (1)

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

   Recommendations

• On the use of decision diagrams for finding repetition-free longest common subsequences 👍 👎
• Algorithms for Computing Variants of the Longest Common Subsequence Problem 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)