Packing Rooted Directed Cuts in a Weighted Directed Graph

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1972
Accession Number
AD0750276

Entities

People

  • D. R. Fulkerson

Organizations

  • Cornell University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Contracts
  • Engineering
  • Equations
  • Flow Network
  • Graphs
  • Inequalities
  • Linear Programming
  • Mathematics
  • Military Research
  • New York
  • Operations Research
  • Real Variables
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.