Finding minimal branchings with a given number of arcs
Dragoš Cvetković, Mirjana Čangalović · Yugoslav journal of operations research · 2002
We describe an algorithm for finding a minimal s-branching (where s is a given number of its arcs) in a weighted digraph with an a symetric weight matrix. The algorithm uses the basic principles of the method (previously developed by J. Edmonds) for determining a minimal branching in the case when the number of its arcs is not specified in advance. Here we give a proof of the correctness for the described algorithm.