Ricerc@Sapienza

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.

The vitality of an arc/node of a graph with respect to the maximum flow between two fixed nodes s and t is defined as the reduction of the maximum flow caused by the removal of that arc/node. In this paper, we address the issue of determining the vitality of arcs and/or nodes for the maximum flow problem. We show how to compute the vitality of all arcs in a general undirected graph by solving only 2(n − 1) max flow instances and, in st‐planar graphs (directed or undirected) we show how to compute the vitality of all arcs and all nodes in O(n) worst‐case time.