Một Thuật Toán Systolic Hiệu Quả cho Bài Toán Dãy Con Chung Dài Nhất
Tóm tắt
Từ khóa
#LCS #Dãy con chung #Thuật toán systolic #Độ phức tạp thời gianTài liệu tham khảo
T. Agerwala, J. L. Martin, J. H. Mirza, D. C. Sadler, D. M. Dias, and M. Snir. SP2 system architecture. IBM Systems Journal, 34:152–184, 1995.
A. Aggarwal and J. Park. Notes on searching in multidimensional monotone arrays. In Proc. 29th Ann. IEEE Symp. Foundations of Comput. Sci., pp. 497–512. IEEE Computer Society. Los Alamitos, Calif., 1988.
A. Aho, D. Hirschberg, and J. Ullman. Bounds on the complexity of the longest common subsequence problem. Journal of the Association for Computing Machinery, 23:1–12, 1976.
A. Apostolico. Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings. Information Processing Letters, 23:63–69, 1986.
A. Apostolico, M. Atallah, L. Larmore, and S. Mcfaddin. Efficient parallel algorithms for string editing and related problems. SIAM Journal on Computing, 19:968–988, 1990.
A. Apostolico, S. Browne, and C. Guerra. Fast linear-space computations of longest common subsequences. Theoretical Computer Science, 92:3–17, 1992.
A. Apostolico and C. Guerra. The longest common subsequence problem revisited. Algorithmica, 2:315–336, 1987.
Y. Feldman and E. Shapiro. Spatial machines: A more realistic approach to parallel computation. Communications of the ACM, 35(10):61–73, 1992.
W. D. Hillis. The Connection Machine. MIT Press, Cambridge, Mass., 1985.
D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6):341–343, 1975.
D. S. Hirschberg. Algorithms for the longest common subsequence problem. Journal of the ACM, 24:664–675, 1977.
S. K. Kumar and C. P. Rangan. A linear-space algorithm for the LCS problem. Acta Informatica, 24:353–362, 1987.
H. T. Kung. Why systolic architectures? IEEE Computer, 15(1):37–46, 1982.
T. Lecroq, G. Luce, and J. F. Myoupo. A faster linear systolic algorithm for recovering a longest common subsequence. Information Processing Letters, 61:129–136, 1997.
Y. C. Lin. New systolic arrays for the longest common subsequence problem. Parallel Computing, 20:1323–1334, 1994.
M. Lu and H. Lin. Parallel algorithms for the longest common subsequence problem. IEEE Transactions on Parallel and Distributed Systems, 5:835–848, 1994.
G. Luce and J. F. Myoupo. An efficient linear systolic algorithm for recovering longest common subsequences. In Proc. IEEE Int. Conf. on Algorithms and Architectures for Parallel Processing, pp. 20–29, 1995.
A. Mukherjee. Hardware algorithms for determining similarity between two strings. IEEE Transactions on Computers, 38:600–603, 1989.
N. Nakatsu, Y. Kambayashi, and S. Yajima. A longest common subsequence algorithm suitable for similar text strings. Acta Informatica, 18:171–179, 1982.
P. Quinton and Y. Robert. Systolic Algorithms & Architectures. Prentice Hall International, Hertfordshire, UK, 1991.
Y. Robert and M. Tchuente. A systolic array for the longest common subsequence problem. Information Processing Letters, 21:191–198, 1985.
D. Sankoff and J. B. Kruskal. Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, Mass., 1983.
P. M. B. Vitanyi. Locality, communication, and interconnect length in multicomputers. SIAM Journal on Computing, 17:659–672, 1988.
R. A. Wagner and M. J. Fischer. The string to string correction problem. Journal of the Association for Computing Machinery, 21:168–173, 1974.
C. B. Yang and R. C. T. Lee. Systolic algorithms for the longest common subsequence problem. Journal of the Chinese Institute of Engineers, 10:691–699, 1987.