The backward edges are the edges from right nodes to the separator nodes or from right nodes to left nodes (edges e 4, e 8 in Fig. 2 ).
In brief, instead of computing the reachability probability from the given source node to the target node, we incrementally compute the reachability probability from the source node to each node separator in sequential order.
So, in what follows by node separator we refer to a good node separator, unless otherwise specified.
Following from Equation (1), our algorithm iteratively computes p K0, K c+1, K c+1) by moving from one node separator to the next, starting from K0. Step 1.
Each of these sets define a subnetwork of G. Once the network is partitioned this way, instead of computing the reachability probability directly from s to t, we compute it incrementally by advancing from one node separator to the next.
3. Proposing prospective separator nodes for approval to the user, implementing the decision and recalculating the DAG with improved blocking, leading to the next round of separator selection.
Since the separator sets, between each pair of the neighboring cliques, are always non-empty, the separator nodes are responsible to perform the communication.
We present an algorithm to construct an edge-separator with extension of O Δnα) from a node-separator of size O(nα).
Since all node particles within the clique have one common weight (e.g., { W C i k, m, X C i k, m } = { W C i k, m, { X t k, m, X u k, m } } ), we can simply pick the particles of separator nodes (from the clique that send the message), and compute the weight as reminder of (6).
A node separator K also partitions the edges of the given network into three subsets: The left edges are the edges between the nodes in the union of left and separator nodes (e.g., edges e 1, e 2, e 3, e 5 and e 6 in Fig. 2 ).
