0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This seems to be an oddly ... specific question. Can you add some background? $\endgroup$
    – Raphael
    Jan 9, 2014 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, 2014 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, 2014 at 15:25

0

Your Answer

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