Accelerated Algorithms for Labelling and Relabelling of Trees, with Application to Distribution Problems.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Statistics and Probability
- Operations Research