Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution Problems
V. Srinivasan, Gerald L. Thompson · Journal of the ACM · 1972
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.This paper offers an improvement over the predecessorindex 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.