Carleton University
Technical Report TR-08-05
March 28, 2008
Efficient maximum subsequence queries and updates for dynamic forests
Bishnu Bhattacharyya & Frank Dehne
Abstract
The problem of efficiently maintaining attributes of a dynamic forest modified by edge insertions and deletions is one that has been extensively studied. In this paper, we present a novel dynamic data structure that supports edge insertions and deletions while maintaining non-local properties in O(log n) time. We use this data structure to solve an important open problem: a dynamic data structure with O(log n) query, insertion, and deletion time for computing maximum subsequences between pairs of query nodes in dynamic forest.