Digraphs of potential barriers: properties of their tree structure and algorithm for constructing minimum spanning forests

Abstract

For a weighted digraph without loops $V$, the arc weights of which can be obtained from an undirected graph with loops $\mathsf{P}$ according to the rule $v_{ij}=p_{ij}-p_{ii}$, the properties are studied. An effective algorithm for constructing directed trees of minimum weight and an algorithm for constructing spanning directed forests of minimum weight are proposed.

32 pages, 3 figures