An approximate A^ algorithm and its application to the SCS problem.

DOI10.1016/S0304-3975(02)00085-3MaRDI QIDQ1401210zbMATH OpenFDO

Authors Gaia Nicosia, Gianpaolo Oriolo

Publication date 17 August 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(02)00085-3

zbMATH Keywords

\(A^{\ast}\) algorithmApproximationShortest common supersequence

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 1859299
• Approximation algorithms for the shortest common superstring problem
• An \(A^\ast\) search algorithm for the constrained longest common subsequence problem
• scientific article; zbMATH DE number 827942
• The constrained shortest common supersequence problem

Cites work

• Enhanced \(A^{*}\) algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases
• scientific article; zbMATH DE number 827942 (Why is no real title available?)
• More on the complexity of common superstring and supersequence problems
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• The shortest common supersequence problem over binary alphabet is NP- complete

Cited in

(6)

• The multi-spreader crane scheduling problem: partitions and supersequences
• Minimum cost multi-product flow lines
• Heuristic shortest path algorithms for transportation applications: state of the art
• Minimum cost paths over dynamic networks
• scientific article; zbMATH DE number 1859299 (Why is no real title available?)
• Flow shop scheduling with inter-stage flexibility and blocking constraints

This page was built for publication: An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.

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