0
$\begingroup$

Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely

  • $\mathsf{move}(v_i, v_j)$: this operator moves $v_i$ to the position immediately after $v_j$; that is, after calling this function, the graph $G$ becomes (if $i > j$) $$ v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_j \rightarrow v_i \rightarrow v_{j+1} \rightarrow \cdots \rightarrow v_{i-1} \rightarrow v_{i+1} \rightarrow \cdots $$

  • $\mathsf{reachable}(v_i, v_j)$: whether $v_j$ is reachable from $v_i$ in $G$; that is, whether there is a path from $v_i$ to $v_j$

My current idea is to arrange $v_1$, $v_2$, $\cdots$, $v_n$ in a balanced binary tree such that if $v_j$ is reachable from $v_i$, then either one of below holds:

  • $v_j$ is in the right subtree of $v_i$;

  • $v_i$ is in the left subtree of $v_j$;

  • there is a node $v_k$ such that $v_i$ is in the left subtree of $v_k$ and $v_j$ is in the right subtree of $v_k$.

Using a balanced BST, we can get the rank of each node and by comparing the ranks of two nodes, we can know whether a node is reachable from another. Therefore, two operations above can be implemented in $O(\log n)$ time.

Q: Is there a better data structure with better complexity please?

$\endgroup$
5
$\begingroup$

Nomenclature aside (a line graph is something different than what you describe), you appear to be describing the problem of ''maintaining order in a list''. You have a list of items $v_i$ (your graph), you can remove an item from one point in the list and re-insert it elsewhere, and you want to check whether one item appears earlier than another in the list. This problem has a constant-time solution; see Dietz and Sleator, "Two algorithms for maintaining order in a list", STOC 1987, https://www.cs.cmu.edu/~sleator/papers/maintaining-order.html and https://en.wikipedia.org/wiki/Order-maintenance_problem

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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