Ricerc@Sapienza

Starting from the work of Bonferroni more than one century ago, several methods have been proposed in the literature for the problem of finding upper bounds for the probability of the union of n events when the individual probabilities of the events as well as the probabilities of all intersections of k-tuples of these events are known. The most popular methods for obtaining bounds are based either on a linear programming formulation of the problem or on graph techniques. Some of the graph-based bounds are based on a greedy algorithm and can be found in polynomial time.

A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected sub- graph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a simple linear time algorithm that, given a maximal planar chordal graph, determines in linear time whether it contains an LCST or not, and produces one if it exists.