5
$\begingroup$

Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it must be possible to insert leaves as well as internal nodes. Deletion is not needed. $M$ can only grow by adding new vertices as they are inserted into $V$ (no existing vertices of $V$ will be added to $M$ at a later point in time).

I need an algorithm that given any vertex $v \in V$ (not necessarily in $M$), it will find the nearest ancestor $u \in M$ of $v$, with space preferably being not worse than linear in $|V|$ and/or $|M|$ and time being somewhat logarithmic in $|M|$. Also the updates should be efficient.

This is known as the Marked Ancestor Problem [1] and also goes under the names of two-dimensional range searching and union-find problems. The problem with [1] is that for once it doesn't support insertion of internal nodes, and also it is extremely abstract and I definitely can't derive an algorithm and an implementation from it.

Also in my case, a solution involving Informative Labeling [2] would be highly desirable.

  • [1] S. Alstrup, T. Husfeldt and T. Rauhe, Marked Ancestor Problems. focs, pp.534, 39th Annual Symposium on Foundations of Computer Science, 1998
  • [2] D. Peleg, Informative labeling schemes for graphs. Mathematical Foundations of Computer Science, pp. 579--588, 2000

Here is another approach, maybe it can be "fixed": I can maintain versions of the tree which are linearized by a total order, one using pre-order traversal, the other using post-order traversal, using an approach developed by Dietz [3]. With these two lists I can query in $O(1)$ whether a vertex $u$ is an ancestor of another vertex $v$ in the tree ($u$ must be left of $v$ in the pre-order list and right of $v$ in the post-order list). If I could organize my vertices $M$ in a way that I can find the nearest ancestor of $v$ in logarithmic or polylogarithmic time, the problem is solved. Right now I can just go through all elements of $M$ and collect the nearest ancestor (closest to $v$ in the lists) in $O(|M|)$...

  • [3] P. Dietz, Maintaining order in a linked list. Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 122--127, 1982
Improve this question
$\endgroup$
5
  • $\begingroup$ What does it mean to "insert an internal node"? $\endgroup$
    – Jeffε
    Apr 21, 2011 at 4:45
  • $\begingroup$ @JeffE -- many approaches make the compromise to allow tree modification only at the leaves. That is, the tree can grow only by adding leaves, or shrink by deleting leaves. Ideally I would be able to insert a vertex between two existing vertices. Of course, this can be simulated by removing the subtree first and and then re-adding all its vertices, but this comes with a huge performance penalty. However -- if I can manage to implement the dynamic version of Alstrup at all, it would already make my project advance quite a bit. So the middle paragraph is the most important one. $\endgroup$
    – 0__
    Apr 21, 2011 at 10:53
  • $\begingroup$ You may be asked to add any vertices to M later, and to handle this you have to remember the tree itself. Therefore any data structure for your task requires Ω(|V|) space (more precisely Ω(|V| log |V|) bits). (This may not apply to schemes based on informative labeling, which I do not know well.) $\endgroup$
    – Tsuyoshi Ito
    Apr 21, 2011 at 11:25
  • $\begingroup$ @Tsuyoshi -- That is correct. I should be more precise here: In fact I have multiple subsets of V, because there are different assignments possible, so there is a subset M, a subset N, etc. So I do keep track of the whole V, but I separately maintain M, N, etc.; each of the sets should require as little space as possible; at worst, it shouldn't grow exponentially, but maximally with a linear factor of the size of the tree or subset. $\endgroup$
    – 0__
    Apr 21, 2011 at 12:08
  • $\begingroup$ I see. That makes more sense. I do not know any answer but hope you get a good answer. $\endgroup$
    – Tsuyoshi Ito
    Apr 21, 2011 at 12:20

1 Answer 1

Reset to default
4
$\begingroup$

If you don't need deletions, I think the first part of Lemma 4.1 on page 349 of the following paper:

Jeffery Westbrook: Fast Incremental Planarity Testing. ICALP 1992: 342-353 http://dx.doi.org/10.1007/3-540-55719-9_86

gives you a linear time algorithm for any sequence of operations consisting of constructing and marking the tree, as well as conducting nearest marked ancestor queries (i.e. the query time is amortized constant).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.