Displaying similar documents to “Enumeration of integral tetrahedra.”

A new practical linear space algorithm for the longest common subsequence problem

Heiko Goeman, Michael Clausen (2002)



This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths m and n , n m , on an alphabet of size s , we first present an algorithm which determines the length p of an LCS in O ( n s + min { m p , p ( n - p ) } ) time and O ( n s ) space. This result has been achieved before [ric94,ric95], but our algorithm is significantly faster than previous methods. We also provide a second algorithm which generates an LCS in O ( n s + min { m p , m log m + p ( n - p ) } ) time while preserving the linear space bound,...

Pivoting algorithm in class of ABS methods

Gabriela Kálnová (1996)

Archivum Mathematicum


Summary: The paper deals with a pivoting modification of the algorithm in the class of ABS methods. Numerical experiments compare this pivoting modification with the fundamental version. A hybrid algorithm for the solution of the linear system with the Hankel matrix is introduced.