Assume having a graph $G_{variables}=(V,U)$ where $V=\{v_1,v_2,…,v_n\}$ is a set of variables; each variable $v_i\in V$ is associated with a set of possible values (it's domain) $dom(v_i)$.

Let $P$ be a search problem (i.e reachability problem) over graph $G=(O,E)$ where $O$ is the cartesian product of the variables domains. Let $T$ be a junction tree resulted from $G_{variables}$. $P$ can be also solved through searching every clique in $T$. I am looking for keywords/examples of such problems. $G_{variables}$ preferably to be DAG.

  • $\begingroup$ This seems to be an oddly ... specific question. Can you add some background? $\endgroup$ – Raphael Jan 9 '14 at 23:14
  • $\begingroup$ What are the edges (so the set $U$) of $G_{\text{variables}}$, i.e. can we assume it is a chordal (di)graph? I'm only curious because I'm not sure if by a junction tree you mean a clique tree and I should be thinking of chordal graphs. $\endgroup$ – Juho Jan 10 '14 at 9:10
  • $\begingroup$ @Juho think of $G_{variables}$ as a DAG (or even undirected graph). To go from $G_{variables}$ to $T$, I need to triangulate $G_{variables}$ (and moralise it if its DAG). $\endgroup$ – seteropere Jan 10 '14 at 15:25

Your Answer

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

Browse other questions tagged or ask your own question.