A faster tree-decomposition based algorithm for counting linear extensions
We consider the problem of counting the linear extensions of an n-element poset whose cover graph has treewidth at most t. We show that the problem can be solved in time Õ(nt+3), where Õ suppresses logarithmic factors. Our algorithm is based on fast multiplication of multivariate polynomials, and so...
Main Authors: | , , |
---|---|
Other Authors: | , , , , |
Format: | Conference Object |
Language: | English |
Published: |
2021
|
Subjects: | |
Online Access: | http://hdl.handle.net/10138/325877 |