EIBEN, Eduard, Robert GANIAN, Kustaa KANGAS and Sebastian ORDYNIAK. Counting Linear Extensions: Parameterizations by Treewidth. Algorithmica. Springer, 2019, vol. 81, No 4, p. 1657-1683. ISSN 0178-4617. Available from: https://dx.doi.org/10.1007/s00453-018-0496-4. |
Other formats:
BibTeX
LaTeX
RIS
@article{1648242, author = {Eiben, Eduard and Ganian, Robert and Kangas, Kustaa and Ordyniak, Sebastian}, article_number = {4}, doi = {http://dx.doi.org/10.1007/s00453-018-0496-4}, keywords = {Parameterized Complexity}, language = {eng}, issn = {0178-4617}, journal = {Algorithmica}, title = {Counting Linear Extensions: Parameterizations by Treewidth}, url = {https://doi.org/10.1007/s00453-018-0496-4}, volume = {81}, year = {2019} }
TY - JOUR ID - 1648242 AU - Eiben, Eduard - Ganian, Robert - Kangas, Kustaa - Ordyniak, Sebastian PY - 2019 TI - Counting Linear Extensions: Parameterizations by Treewidth JF - Algorithmica VL - 81 IS - 4 SP - 1657-1683 EP - 1657-1683 PB - Springer SN - 01784617 KW - Parameterized Complexity UR - https://doi.org/10.1007/s00453-018-0496-4 L2 - https://doi.org/10.1007/s00453-018-0496-4 N2 - We consider the #P-complete problem of counting the number of linear extensions of a poset (#LE); a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of #LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that #LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Algorithms. On the positive side we show that #LE becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph. ER -
EIBEN, Eduard, Robert GANIAN, Kustaa KANGAS and Sebastian ORDYNIAK. Counting Linear Extensions: Parameterizations by Treewidth. \textit{Algorithmica}. Springer, 2019, vol.~81, No~4, p.~1657-1683. ISSN~0178-4617. Available from: https://dx.doi.org/10.1007/s00453-018-0496-4.
|