GANIAN, Robert, Sebastian ORDYNIAK, Eduard EIBEN and Kanga KUSTAA. Counting Linear Extensions: Parameterizations by Treewidth. Online. In Piotr Sankowski and Christos D. Zaroliagis. 24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24, 2016, Aarhus, Denmark. Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, p. 1-18. ISBN 978-3-95977-015-6. Available from: https://dx.doi.org/10.4230/LIPIcs.ESA.2016.39. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1376045, author = {Ganian, Robert and Ordyniak, Sebastian and Eiben, Eduard and Kustaa, Kanga}, address = {Aarhus, Denmark}, booktitle = {24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24, 2016, Aarhus, Denmark}, doi = {http://dx.doi.org/10.4230/LIPIcs.ESA.2016.39}, editor = {Piotr Sankowski and Christos D. Zaroliagis}, keywords = {treewidth; linear extensions}, howpublished = {elektronická verze "online"}, language = {eng}, location = {Aarhus, Denmark}, isbn = {978-3-95977-015-6}, pages = {1-18}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, title = {Counting Linear Extensions: Parameterizations by Treewidth}, year = {2016} }
TY - JOUR ID - 1376045 AU - Ganian, Robert - Ordyniak, Sebastian - Eiben, Eduard - Kustaa, Kanga PY - 2016 TI - Counting Linear Extensions: Parameterizations by Treewidth PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik CY - Aarhus, Denmark SN - 9783959770156 KW - treewidth KW - linear extensions 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 com- plexity 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 xed- parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Al- gorithms. On the positive side we show that #LE becomes xed-parameter tractable parameterized by the treewidth of the incomparability graph. ER -
GANIAN, Robert, Sebastian ORDYNIAK, Eduard EIBEN and Kanga KUSTAA. Counting Linear Extensions: Parameterizations by Treewidth. Online. In Piotr Sankowski and Christos D. Zaroliagis. \textit{24th Annual European Symposium on Algorithms, $\{$ESA$\}$ 2016, August 22-24, 2016, Aarhus, Denmark}. Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, p.~1-18. ISBN~978-3-95977-015-6. Available from: https://dx.doi.org/10.4230/LIPIcs.ESA.2016.39.
|