Project

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

Duration
01 October 2010 → 15 May 2013
Funding
Regional and community funding: Special Research Fund
Research disciplines
  • Natural sciences
    • Applied mathematics in specific fields
Keywords
algorithms comparability graphs partially ordered sets
 
Project description

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