An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.

DOI10.1016/S0304-3975(02)00085-3zbMath1044.68033MaRDI QIDQ1401210

Gianpaolo Oriolo, Gaia Nicosia

Publication date: 17 August 2003

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

zbMATH Keywords

Approximation\(A^{\ast}\) algorithmShortest common supersequence

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (4)

Minimum cost paths over dynamic networks ⋮ 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

Cites Work

• Unnamed Item
• The shortest common supersequence problem over binary alphabet is NP- complete
• Enhanced \(A^{*}\) algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases
• More on the complexity of common superstring and supersequence problems
• The Complexity of Some Problems on Subsequences and Supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

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