An Improved Method of Finding All Largest Combinable Classes
G. Jack Lipovski · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1967
Several algorithms, such as a row-column minimization algorithm and an asynchronous machine assignment algorithm, require finding the largest sets of combinable elements from a list of pairwise combinable elements.This paper presents a technique for finding these sets which is generally faster than the one presently in use.Further, the presentation of this technique uncovers an interesting theory about combinability.AN IMPROVED METHOD OF FINDING ALL LARGEST COMBINABLE CLASSES.. I. Introduction Several algorithms require a step in which one finds the largest sets of combinable elements from a listing of pairwise combinable elements.Of particular interest is the determination of R-classes and C-classes in row-column minimization of a sequential machine, [l] and the determination of prime partitions in the racefree assignment of asynchronous machines [2 ].(The latter problem can be handled with some modification, which the author intends to study in another paper.)Essential to this problem is a listing of given pairs of combinable elements, from which sets of elements will be found, such that every pair of elements in the set is combinable, and no pair is not combinable.Evidently, this problem is quite general, and will likely find its way into future algorithms.There is, at present, a respectable technique for solving this problem.The listing of combinable pairs is examined to locate three pairs, such that the three elements in the pairs form a triplet; the triplets are compared to grow larger classes, and this iterative process of inspection, combination, and possibly deletion, continues until no new (n+1)-tuples are found when all n-tuples have been examined.From a different point of view entirely, another method can be found which avoids exhaustive comparisons.It is of theoretical interest of itself, because it imparts a curious, but real and important, Boolean interpretation to this problem.A Boolean inter pretation enables a problem, which is very near to the type of problem we shall investigate, to be divided up into our problem and one which is simpler than the original, but most significantly, this new method is generally faster, and requires less core memory space in its programmed f'orrii, than the original method.II.A Negative Approach One conventionally considers combinable pairs, rather than considering the other pairs.This is similar to mentioning which pairs among a group of girls are friends, rather than which are enemies.Let us, then, find the collection of parties that might be given on an important prom weekend, such that each party contains the largest group of girls, none of which are enemies.We are not demanding that a girl stays at the same party all night, but may go to several.While this example is light, if not humorous, it serves to indicate the generality of the problem.We know five girls, Alice (A), Betty (B), Carol (C), Donna (D) and Ellen (E).Alice gets along with Carol, and with Ellen; Donna, with Betty, with Carol, and with Ellen; and Carol and Ellen are friends.The other pairs are not.But in our negative approach, we obviously have given, by omission^pairs of enemies: (Alice, Betty), (Alice, Donna), (Betty, Carol) and (Ellen, Betty).We shall turn our attention