SET OF CUT SETS AND OPTIMUM FLOW,
Abstract
An important unsolved problem in the theory of communication nets is the enumeration of the properties of a set of edge flows necessary to give a required terminal flow from one vertex to another. For example, there is no simple method for obtaining a set of edge flows to give maximum terminal flow. The relationship of these flows and the conditions necessary to obtain maximum flow are important practical problems in systems in which edge flow is limited; in the telephone system for example. Clearly an improvement would result if it were possible to reduce some edge flows and still maintain the same terminal flow. The method presented stems from the work of Ford and Fulkerson which relates maximum terminal flow to the cut set separating the terminals. A new set of cut sets called a 'set of M-cut sets' is introduced from which it is possible to improve edge flows while maintaining maximum terminal flow.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1965
- Accession Number
- AD0625200
Entities
People
- Mac E. Van Valkenburg
- Wataru Mayeda
Organizations
- University of Illinois Urbana–Champaign