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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE