Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence

DOI10.1016/j.tcs.2009.03.027zbMath1175.68302OpenAlexW2047982179MaRDI QIDQ1029349

Yoshifumi Sakai

Publication date: 10 July 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.027

zbMATH Keywords

algorithmslongest common subsequencetopological sort

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Algorithms on strings (68W32)

Uses Software

• ClustalW

Cites Work

• Unnamed Item
• Unnamed Item
• Semi-local longest common subsequences in subquadratic time
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• A simple algorithm for the constrained sequence problems
• A linear space algorithm for computing maximal common subsequences
• A fast algorithm for computing longest common subsequences
• Algorithms on Strings, Trees and Sequences
• Multiple alignment of biological sequences with gap flexibility

This page was built for publication: Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence