The Complexity of Partial Orders

We will address several issues, old and new, in the computational complexity of comparison based problems, focusing on the long term development of techniques. Most notably, we will look at the comparison minimization problems of placing a set of n values into an arbitrary given partial order, and of completing the sort from this stage. The parallel development of the algorithmics and of graph entropy will be discussed in this context.

J. Ian Munro, University of Waterloo, Canada

Donate · Contact Us · Site Map · Join SIAM · My Account