Advanced search

Project: Algorithms on posets and comparability graphs: enumeration, transitive orientation and stochastic dominance extension.

01-OCT-10 – 30-SEP-13

In this project posets and other related mathematical structres such as comparability graphs, which can be seen as a generalization of posets, will be studied. In particular, the problem of efficiently enumerating all structures of given size will be addressed. Furthermore, a study of how all posets corresponding to the transitive orientations of such a comparability graph can be generated efficiently will be made. Finally, we will study extensions of a poset obtained by using stochastic dominance of the rank probability distributions of the elements of a poset