TY - BOOK
TI - MinMax Interval Trees
AU - Karim, Md Enamul
AB - We design a MinMax interval tree, a data structure that stores a given integer sequence using a set of Min and Max nodes. For a sequence of length n, computation of its MinMax interval tree requires O( n) time and space. All K intervals of a given sequence can be enumerated from its MinMax interval tree at a cost of O( K). We also introduce a model for gapped intervals and compute the gapped intervals from a MinMax tree at a cost of O( n). Transitively reduced partial orders of the elements in the Min nodes of a MinMax tree can be derived from the tree at a cost of O(n). We also show that MinMax intervals trees for k different permutations can be merged at a cost of O( kn). The merged tree can be used to enumerate all common intervals of k permutations and to derive transitively reduced partial order relationship for elements in the Min nodes for all permutations using the same costs as required by a tree for a single permutation. We also show how we can extract the irreducible intervals and the PQ tree from a MinMax tree in O(n) time. Common intervals and partial order relationship of the elements of permutations have direct applications in wide range of areas including genome mining, preference based ordering and content sensitive cross over operations in genetic algorithms.
DA - 2007///
PY - 2007
DP - Google Books
SP - 58
LA - en
PB - ProQuest
SN - 9780549395225
ER -