Variations on an Ordering Theme with Constraints
Walter Guttmann, Markus Maucher · 2006
We investigate the problem of finding a total order of a finite set that satisfies various local ordering constraints. Depending on the admitted constraints, we provide an efficient algorithm or prove NP-completeness. We discuss several generalisations and systematically classify the problems.