TY - JOUR
T1 - A linear space algorithm for computing a longest common increasing subsequence
AU - Sakai, Yoshifumi
PY - 2006/9/15
Y1 - 2006/9/15
N2 - Let X and Y be sequences of integers. A common increasing subsequence of X and Y is an increasing subsequence common to X and Y. In this note, we propose an O (| X | ṡ | Y |)-time and O (| X | + | Y |)-space algorithm for finding one of the longest common increasing subsequences of X and Y, which improves the space complexity of Yang et al. [I.H. Yang, C.P. Huang, K.M. Chao, A fast algorithm for computing a longest common increasing subsequence, Inform. Process. Lett. 93 (2005) 249-253] O (| X | ṡ | Y |)-time and O (| X | ṡ | Y |)-space algorithm, where | X | and | Y | denote the lengths of X and Y, respectively.
AB - Let X and Y be sequences of integers. A common increasing subsequence of X and Y is an increasing subsequence common to X and Y. In this note, we propose an O (| X | ṡ | Y |)-time and O (| X | + | Y |)-space algorithm for finding one of the longest common increasing subsequences of X and Y, which improves the space complexity of Yang et al. [I.H. Yang, C.P. Huang, K.M. Chao, A fast algorithm for computing a longest common increasing subsequence, Inform. Process. Lett. 93 (2005) 249-253] O (| X | ṡ | Y |)-time and O (| X | ṡ | Y |)-space algorithm, where | X | and | Y | denote the lengths of X and Y, respectively.
KW - Algorithms
KW - Longest common subsequence
KW - Longest increasing subsequence
UR - http://www.scopus.com/inward/record.url?scp=33745333981&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33745333981&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2006.05.005
DO - 10.1016/j.ipl.2006.05.005
M3 - Article
AN - SCOPUS:33745333981
SN - 0020-0190
VL - 99
SP - 203
EP - 207
JO - Information Processing Letters
JF - Information Processing Letters
IS - 5
ER -