On some complexity properties of N-free posets and posets with bounded decomposition diameter (Q1086264): Difference between revisions

Among generalizations of series-parallel posets, the N-free posets are much better known than posets with bounded decomposition diameter, i.e., those posets iteratively built up by substitution from posets of cardinality at most k. Nevertheless, the authors demonstrate that the latter class may well be the better one for a variety of combinatorial optimization problems and other reasons. Thus, although the jump-number problem is shown to be polynomially solvable on both classes, the isomorphism problem and the 1/prec/\(\sum w_ jC_ j\) scheduling problem are here demonstrated to be among these which are only polynomially solvable for the second class. As an early exponent of the merits of the substitution technique, this author finds the success of the method more than only interesting. Since the subject is still in a process of evolving its main outlines, this paper will make an important difference in the direction of eventual development. To the extent that it will be superseded by further results, its very success will make its view more commonplace.