Searching in Dynamic Tree-Like Partial Orders

Details Searching in Dynamic Tree-Like Partial Orders Searching in Dynamic Tree-Like Partial Orders

2010-10-07

arxiv.org/abs/1010.1316v2

Computer Science

Data Structures and Algorithms

51 pages, 30 figures

Scientific paper

We give the first data structure for the problem of maintaining a dynamic set of n elements drawn from a partially ordered universe described by a tree. We define the Line-Leaf Tree, a linear-sized data structure that supports the operations: insert; delete; test membership; and predecessor. The performance of our data structure is within an O(log w)-factor of optimal. Here w <= n is the width of the partial-order---a natural obstacle in searching a partial order.

Affiliated with

Also associated with

No associations

Rating

Searching in Dynamic Tree-Like Partial Orders does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Searching in Dynamic Tree-Like Partial Orders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Searching in Dynamic Tree-Like Partial Orders will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-508737