LEcount

LEcount is a software for counting linear extensions of partially ordered sets (posets). It includes a collection of algorithms, which are documented in the paper Counting linear extensions of sparse posets (IJCAI'16). LEcount and the posets used in the empirical evaluation of the algorithms are available for download:

LEcount 16.04.20

LEcount is written in C++ and currently requires the GNU C++ compiler (G++) and the GMP and Boost libraries. The current version contains cursory instructions for running each algorithm presented in the paper (see readme.txt).

Experiment posets

The posets are named as follows:

• avgdeg_n_k: Posets on n elements of average degree k.
• maxindeg_n_k: Posets on n elements of maximum in-degree k.
• bipartite_n_p: Bipartite posets on n+n elements of average density p.
• gridtree_n_t: Grid tree posets on n elements of treewidth t.

Each poset is represented as a 0-1 matrix, where a 1 at [i,j] indicates i < j.