The Minimum Weight Rooted Aborescence Problem: A Branch and Bound Solution

A Subgraph S of a rooted acyclic graph G is called a rooted arborescence if (a) S contains the root as one of its vertices, (2) S is connected, and (3) No two arcs of S are directed towards the same vertex. This paper studies the problem of finding a minimum weight rooted arborescence in a rooted acyclic graph with weights on nodes. This problem is related to the incapacitated plant location problem. A branch and bound method is developed for this problem, and computational results are reported.