Accelerated Algorithms for Labelling and Relabelling of Trees, with Application to Distribution Problems.
Abstract
Adjacent extreme point problems involving a tree basis (e.g., the transportation problem) require the determination of cycles which are created when edges not belonging to the basis are added to the basis-tree. The present paper offers an improvement over the predecessor-index method for finding such cycles and involves the use of a distance function defined on the nodes of the tree, in addition to the predecessor labels. It is shown that the relabeling associated with a basis change can be minimized by defining yet another function called the successor function. The algorithms for labeling and relabeling are then specialized for the specific case of transportation problems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1970
- Accession Number
- AD0723196
Entities
People
- Gerald L. Thompson
- V. Srinivasan
Organizations
- Carnegie Mellon University