Polytrees
A network is singly connected (a polytree) if it contains no undirected loops.
Theorem: Inference in a singly connected network can be done in linear time*.
Main idea: in variable elimination, need only maintain distributions over single nodes.
* in network size including table sizes.