Counting Linear Extensions of Restricted Posets
Counting Linear Extensions of Restricted Posets
复制标题
计算受限偏集的线性扩展
DOI：
--
复制
发表时间：
2018
影响因子：
0.7
通讯作者：
I. Pak
中科院分区：
文献类型：
--
作者：
Samuel Dittmer;I. Pak
我们证明了Brightwell和Winkler在1991年提出的一个猜想：计算高度为2的偏序集的线性扩张的个数是P-完全的。我们进一步将这个结果推广到图的关联偏序集。
We prove the 1991 conjecture by Brightwell and Winkler that counting the number of linear extensions for posets of height two is #P-complete. We further extend this result to incidence posets of graphs.