Counting Linear Extensions of Sparse Posets
Abstract
We present two algorithms for computing the number of linear extensions of a given n-element poset. Our first approach builds upon an O(2n n)-time dynamic programming algorithm by splitting subproblems into connected components and recursing on them independently. The recursion may run over two alternative subproblem spaces, and we provide heuristics for choosing the more efficient one. Our second algorithm is based on variable elimination via inclusion-exclusion and runs in time O(nt+4)), where t is the treewidth of the cover graph. We demonstrate experimentally that these new algorithms outperform previously suggested ones for a wide range of posets, in particular when the posets are sparse. PDF
Cite
Text
Kangas et al. "Counting Linear Extensions of Sparse Posets." International Joint Conference on Artificial Intelligence, 2016.Markdown
[Kangas et al. "Counting Linear Extensions of Sparse Posets." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/kangas2016ijcai-counting/)BibTeX
@inproceedings{kangas2016ijcai-counting,
title = {{Counting Linear Extensions of Sparse Posets}},
author = {Kangas, Kustaa and Hankala, Teemu and Niinimäki, Teppo Mikael and Koivisto, Mikko},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2016},
pages = {603-609},
url = {https://mlanthology.org/ijcai/2016/kangas2016ijcai-counting/}
}