Accession Number:
AD0750276
Title:
Packing Rooted Directed Cuts in a Weighted Directed Graph
Descriptive Note:
Technical rept.
Corporate Author:
CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH
Personal Author(s):
Report Date:
1972-09-01
Pagination or Media Count:
22.0
Abstract:
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.
Descriptors:
Subject Categories:
- Operations Research