The longest common subsequence problem for sequences with nested arc annotations.
type: Item
instance of: scholarly article
title: The longest common subsequence problem for sequences with nested arc annotations.
zbMATH Open document ID: 1059.68023
DOI: 10.1016/S0022-0000(02)00004-1
author: Zhi-Zhong Chen
author: Tao Jiang
author: Jianjun Wen
author: Guohui Lin
published in: Journal of Computer and System Sciences
publication date: 2003-05-14T00:00:00Z
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 92D20
zbMATH DE Number: 1910844
zbMATH Keywords: Sequence annotation
zbMATH Keywords: Longest common subsequence
zbMATH Keywords: Book embedding
zbMATH Keywords: NP-hardness
zbMATH Keywords: Approximation algorithm
zbMATH Keywords: Polynomial-time approximation scheme
MaRDI profile type: Publication
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Q4252281
cites work: On triangulating planar graphs under the four-connectivity constraint
cites work: Q4734761
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
cites work: Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Some simplified NP-complete graph problems
cites work: Algorithms on Strings, Trees and Sequences
cites work: Algorithms for the Longest Common Subsequence Problem
cites work: Q2723948
cites work: Near optimal multiple alignment within a band in polynomial time
cites work: Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
cites work: The String-to-String Correction Problem
cites work: Embedding planar graphs in four pages
cites work: Q3024817
full work available at URL: s0022-0000(02)00004-1
OpenAlex ID: W2067194564
Recommended article: Q4535038
Recommended article: The longest common subsequence problem for arc-annotated sequences
Recommended article: Q2723948
Recommended article: Q4737693
Recommended article: A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs
Recommended article: The longest common subsequence problem revisited
Recommended article: Q4918894
Recommended article: On the longest common parameterized subsequence
description: scientific article; zbMATH DE number 1910844