Theoretical Computer Science Asked by jackb on October 30, 2021
Given a (directed) n-tree $T=(N,E,r)$ rooted in $rin N$, I want to represent each node $nin N$ at most as a $m$-dimensional vector $v_nin mathbb{R}^m$ (From the current Yuri’s reply, m cannot be $b$). In particular, given $h$ the height of the tree (that is, the maximum path length starting from $r$), I want to guarantee that $forall a,bin N. |v_a-b_b|_2leq h$ if and only if there exists a directed path $pi(a,b)$ or $pi(b,a)$ in $T$.
Example, given the following tree rooted in $1$, $({1,2,3,4},;{(1,2), (1,3),(3,4)},1)$, I would instantiate the distance constraints as follows:
I was thinking to reduce this problem into the Distance Geometry Problem, and to use the former distances to feed known solvers like DGSOL or MD-Jeep: while the first commits non-negligible errors, MD-Jeep returns some errors during the computation of the torsion angle, and therefore cannot provide a viable solution. Is this a problem of the Distance Geometry Problem itself, or are there other implementations that would not suffer from the same problem? Alternatively, is it possible to express this problem using mathematical programming, i.e. using one of the already existing libraries?
For a directed tree, it is possible to find an embeeding in a n-dimensional space, where n is the maximum branching factor of the tree. This approach could be also generalized for (rooted) DAGs.
More to come in the forthcoming paper: https://www.researchgate.net/publication/342902961_Hierarchical_Embedding_for_DAG_Reachability_Queries
Answered by jackb on October 30, 2021
This is not possible if the dimension $m$ is fixed. Consider a complete $b$-ary tree, in which all edges are oriented from the root $r$. Then all vertices lie in a ball of radius $h$ around $v_r$. On the other hand, the distance between every two leaves is greater than $h$. Since there are $N = b^h$ leaves, we get that
there are $N$ points in a ball of radius $h$ such that all the pairwise distances between the points are greater than $h$
We must have that $m = Omega(log N) = Omega(h log b)$.
Answered by Yury on October 30, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP