I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form return any leaf of $T$ that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$? More informally, the restriction is that when the edge is given, we can only proceed in to that direction.
I can simply perform a DFS and return a leaf found. I think this would take $O(d)$ time, where $d$ is the diameter of $T$. However, I'd like to answer a query in $O(1)$ time. Moreover, I'd only like to allow linear preprocessing time. My idea for achieving this was to use a DFS, label leaves, and then label edges when the search backtracks. This idea might work with some additional effort, but I'm really unsure about the details.
"Graph reachability" turned up some results, but maybe they are dealing with more complex problems. I'm happy with any method that uses $O(n+m)$ preprocessing time and answers the queries in $O(1)$ time.
Asked By : user9214
Answered By : D.W.
Yes, I think you can do this in $O(1)$ time. I outline a method below. There's probably a simpler way to do it, but the following should suffice.
Preprocessing. I'll assume we can view your tree as a rooted tree, with some root. In pre-processing, annotate each internal node $w$ with one example of a leaf that is a descendant of $w$. This can be done in $O(n+m)$ pre-processing time, using a very simple top-down traversal (DFS).
Also, define $p^*(\cdot)$ recursively as follows: if $w$ has any siblings, then $p^*(w)=w$; otherwise, $p^*(w)=p^*(v)$ where $v$ is the parent of $w$; and $p^*(r)=r$, where $r$ is the root of $T$. In English, $p^*(w)$ is defined to be the node obtained by starting at $w$ and continuing upwards until we reach a node that has two or more children (or the root). In pre-processing, we'll compute the value of $p^*(w)$ for each node $w$ and store it associated with $w$. This too can be computed in $O(n+m)$ time.
Answering a query. Now, here's how to answer the query return any leaf that is reachable from $v$ with a path including $(u,v)$, and no other edges incident to $v$:
Case 1: Suppose $u$ is a child of $v$. Then, answering your query amounts to returning any leaf that is a descendant of $u$. This can be done in $O(1)$ time using the annotation on $u$.
Case 2: Suppose $u$ is the parent of $v$, and $u$ has at least one other child. Then, look at any other child of $u$, call it $w$. Then, answering your query amounts to returning any leaf that is a descendant of $w$. This can be done in $O(1)$ time using the annotation on $w$.
Case 3: Suppose $u$ is the parent of $v$, and $u$ has no other children. Then let $u'=p^*(u)$ and let $w$ be any other child of $u'$ (not an ancestor of $v$). Then, answering your query amounts to returning any leaf that is a descendant of $w$. This can be done in $O(1)$ time using the annotation on $w$.
In all three cases, the answer to the query can be computed in $O(1)$ time.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13316
0 comments:
Post a Comment
Let us know your responses and feedback