Packing Rooted Directed Cuts in a Weighted Directed Graph
CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
A simple algorithm is described for constructing a maximum packing of cuts directed away from a distinguished vertex, called the root, in a directed graph each of whose edges has a nonnegative weight, and it is shown that the maximum packing value is equal to the weight of a minimum-weight spanning arborescence directed away from the root.
- Operations Research