Accession Number : AD0723196
Title : Accelerated Algorithms for Labelling and Relabelling of Trees, with Application to Distribution Problems.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Srinivasan,V. ; Thompson,Gerald L.
Report Date : DEC 1970
Pagination or Media Count : 31
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)
Descriptors : (*OPERATIONS RESEARCH, TRANSPORTATION), (*GRAPHICS, THEORY), ALGORITHMS, SET THEORY, DISTRIBUTION FUNCTIONS
Subject Categories : Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE