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
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE