algorithms:minimumcutset

**This is an old revision of the document!**

The Minimum Cut Set algorithm finds a partition of the network into two disconnected parts such as the sum of the weights of the cut is minimum. If no weight is provided, a default value of 1 is assumed and the algorithm searches the minimum number of links whose removal disconnects the graph. The network must be undirected and connected with no parallel edges.

The Minimum Cut Set of a network may not be unique. Since the algorithm starts from a single node, varying this initial node can lead to different cut sets.

This metric creates a new node property to identify the two parts of the partition. It also creates a link property that identifies the links that belong to the Minimum Cut Set (the links that would have to be removed).

Input parameter | Type | Default | Description |
---|---|---|---|

Initial Node* | text | Compulsory | Node Label of the initial node. |

Link Weight | text | None | Link property acting as weight for the distance calculations. Must be positive numbers. |

Property name | text | MinimumCutSet | Name of the link and node property (output). |

* *Required Field*

** References **

- M.E.J. Newman, Networks, an introduction, Oxford University Press, 2010, ISBN: 978-0-19-920665-0, sec. 10.5.

- Wikipedia: Minimum Cut

algorithms/minimumcutset.1548416215.txt.gz · Last modified: 2019/01/25 11:36 by systems