Ordered sets

In the late 1980s I became interested in how one can sort data if one knows some order constraints already. Because of the information- theoretic lower bound the complexity of these sorting problems is related to the number of linear extensions of the partially ordered set determined by the constraints. Computing this number is, in general, #P-complete but I found some classes of posets for which there were efficient algorithms. There were also a few spin-off results deriving from these studies.

Papers on ordered sets

  1. Zigzag permutations and comparisons of adjacent elements, Information Processing Letters 21 (1985), 187-189.
  2. Computing the number of mergings with constraints, Information Processing Letters 24 (1987), 289-292 (with H.W. Chang).
  3. On the width of an orientation of a tree, Order 5 (1988), 33-43 (with D.T.H. Ng).
  4. Sorting with powerful primitive operations, J. Comb. Math. and Comb. Comp. 4 (1989), 29-36 (with D. Nussbaum).
  5. On computing the number of linear extensions of a tree, Order 7 (1990), 23-25.
  6. The recursive structure of some ordering problems, BIT 31 (1991), 194-201.
  7. Partial orders and comparison problems, Sixteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, (Boca Raton, February 1985), Congressus Numerantium 47, 77-88.
  8. Extensions of partial orders of bounded width, (Winnipeg, October 1985), Congressus Numerantium 52, 21-35 (with H.W. Chang).
  9. Partially ordered sets and sorting, Proceedings of the Institute of Mathematics and its Applications Conference on Computers in Mathematical Research (Cardiff, September 1986), Clarendon Press (Oxford 1988), 161-176.
  10. The complexity of order, Proceedings of the 1987 NATO Advanced Study Institute on Algorithms and Order (Ottawa, May 1987), Reidel 1989, 195-230.