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 asymetric 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. | Yugoslav Journal of Operations Research 12 (2002), Number 1, 1-10 FINDING MINIMAL BRANCHINGS BRANCHINGS WITH A GIVEN NUMBER OF ARCS Drago{ CVETKOVI] Faculty of Electrical Engineering University of Belgrade, Belgrade, Yugoslavia Mirjana ^ANGALOVI] Faculty of Organizational Sciences University of Belgrade, Belgrade, Yugoslavia Abstract: 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 asymetric 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. Key words: Combinatorial optimization, weighted graphs, minimal branching. 1. INTRODUCTION We consider an arc weighted digraph G without loops and with an asymmetric weight matrix. As usual, the weight d ( H ) of any subgraph H of G is defined to be the sum of weights of arcs of H . We start with some specific definitions. Definition 1. A tree in which each edge is directed (so that it becomes an arc) is called a directed tree. tree Definition 2. A directed tree is called an arborescence if the following conditions are fulfilled: 1. There is a node x with no entering arcs; 2. Exactly one arc enters each of the other nodes. Node x is called the root. root 2 D. Cvetkovi}, M. ^angalovi} / Finding Minimal Branchings with a Given Number of Arcs Definition 3. A digraph whose weakly connected components are arborescences is called a branching. branching. branching A branching with s arcs is called an s -branching branching We consider the problem of finding a minimal s -branching in G , . a branching with minimal weight. An algorithm for this problem has been developed in [6] (see also [8], pp. 59-61) and we describe it here. The algorithm uses the basic principles of a method for determining a minimal branching .
