What Makes the Arc-Preserving Subsequence Problem Hard?

DOI10.1007/11567752_1zbMath1133.92312OpenAlexW4214861388MaRDI QIDQ5449952

Stéphane Vialette, Romeo Rizzi, Guillaume Fertin, Guillaume Blin

Publication date: 19 March 2008

Published in: Transactions on Computational Systems Biology II (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.74.634

zbMATH Keywords

Computational complexityRNA structuresArc-Preserving Subsequence problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biochemistry, molecular biology (92C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Fast arc-annotated subsequence matching in linear space ⋮ Finding common structured patterns in linear graphs

This page was built for publication: What Makes the Arc-Preserving Subsequence Problem Hard?