A Comparison of Algorithms for Minimizing Bumps in Linear Extensions of Partial Orders

The notion of bumps deals with a property of linear extensions of a partial order. Let P define a partial order on a set X and let L define a linear extension of P. A bump occurs whenever elements x and y in X have x covering y in P and x adjacent to y in L. Heuristics have been developed to construct linear extensions of a partial order that should tend to minimize bumps. This paper presents results of a computer simulation study that compares the performance of bump minimizing algorithms.