Decomposition of a network into minimally connected parts (Q759664)

We investigate the decomposition of a weighted graph into connected subgraphs with minimal weight of the external edges. The problem is treated in the framework of constructing a multicomponent network with the desired graph structure on a given network. An implicit enumeration algorithm is proposed for solving the problem. Characteristic features of the algorithm include the use of adaptive branching strategy and the specific bounding principle used.