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

01/06/1984

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

V. Venkata Rao and Ginnia L F Mc

Working Papers

  • facebook
  • linkedin
  • twitter
  • whatsapp

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.

IIMA