Decomposition of a network into minimally connected parts

MaRDI QIDQ759664zbMATH OpenFDO

Authors A. B. Boronin, O. Yu. Pershin

Publication date 1984

Published in Automation and Remote Control (Search for Journal in Brave)

zbMATH Keywords

adaptive branching strategybounding principleconnected subgraphsdecomposition of a weighted graphimplicit enumeration algorithmminimal weight of the external edgesmulticomponent network

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Integer programming (90C10) Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 3902687
• scientific article; zbMATH DE number 3922710
• scientific article; zbMATH DE number 3887732
• scientific article; zbMATH DE number 1300393
• Minimal graph cuts on network subgraphs

Cited in

(8)

• scientific article; zbMATH DE number 3887732 (Why is no real title available?)
• scientific article; zbMATH DE number 3902687 (Why is no real title available?)
• scientific article; zbMATH DE number 3916183 (Why is no real title available?)
• scientific article; zbMATH DE number 3922710 (Why is no real title available?)
• scientific article; zbMATH DE number 4045674 (Why is no real title available?)
• scientific article; zbMATH DE number 1203273 (Why is no real title available?)
• VERTEX DECOMPOSITION TO CALCULATE THE NETWORK PROBABILISTIC CONNECTIVITY
• A Voronoi heuristic approach to dividing networks into equal-sized sub-networks

This page was built for publication: Decomposition of a network into minimally connected parts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q759664)