Linear-Time Construction of Two-Dimensional Suffix Trees

The two-dimensional suffix tree of a matrix A is a compacted tree that represents all square submatrices of  A . We present the first complete version of a deterministic linear-time algorithm to construct the two-dimensional suffix tree by applying a divide-and-conquer approach.

Saved in:
Bibliographic Details
Published in:Algorithmica 2011-02, Vol.59 (2), p.269-297
Main Authors: Kim, Dong Kyue, Na, Joong Chae, Sim, Jeong Seop, Park, Kunsoo
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computer Science
Computer science
control theory
systems
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Exact sciences and technology
Mathematics of Computing
Theoretical computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The two-dimensional suffix tree of a matrix A is a compacted tree that represents all square submatrices of  A . We present the first complete version of a deterministic linear-time algorithm to construct the two-dimensional suffix tree by applying a divide-and-conquer approach.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-009-9350-z