Accession Number:

ADA011840

Title:

On Edge-Disjoint Branchings

Descriptive Note:

Technical rept.

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH

Personal Author(s):

Report Date:

1975-06-01

Pagination or Media Count:

13.0

Abstract:

Edmonds has given a complicated algorithmic proof of a theorem characterizing directed graphs that contain k edge-disjoint branchings having specified root sets. Tarjan has described a conceptually simple and good algorithm for finding such branchings when they exist. Tarjans algorithm is based on a lemma implicit in Edmonds results. A simple direct proof of this lemma is given, thereby providing a simpler proof of Edmonds theorem and a simpler proof that Tarjans algorithm works.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE