User Tools

Site Tools


algorithms:minimumcutset

This is an old revision of the document!


Minimum Cut Set

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*textCompulsoryNode Label of the initial node.
Link WeighttextNoneLink property acting as weight for the distance calculations. Must be positive numbers.
Property nametextMinimumCutSetName 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