Optimum branchings

Abstract

An arborescence T is a tree whose edges a re directe d so that eac h is directed toward a differe nt node. Exactly one node of T, called the root , has no edge of T directed toward it. Le t C be any directe d grap h with a real numerical weight on eac h edge. A good algorithm is described for find ing in C (if there is one) a s panning arborescence, with prescribed root, whose ed ges have maximum (o r minimum) total weight.