Parameterized complexity of the arc-preserving subsequence problem

DOI10.1007/978-3-642-16926-7_23MaRDI QIDQ3057629zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Ildikó Schlotter

Publication date 16 November 2010

Published in Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16926-7_23

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• Computational Science – ICCS 2005
• What Makes the Arc-Preserving Subsequence Problem Hard?
• Pattern matching for arc-annotated sequences
• Arc-preserving subsequences of arc-annotated sequences

Cites work

• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
• Computational Science – ICCS 2005
• Computing similarity between RNA structures
• Computing the similarity of two sequences with nested arc annotations
• scientific article; zbMATH DE number 2185647 (Why is no real title available?)
• Parametrized complexity theory.
• Pattern matching for arc-annotated sequences
• The longest common subsequence problem for arc-annotated sequences
• The longest common subsequence problem for sequences with nested arc annotations.

Cited in

(2)

• Computational Science – ICCS 2005
• A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs

This page was built for publication: Parameterized complexity of the arc-preserving subsequence problem

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