| GANIAN, Robert, Sebastian ORDYNIAK, Eduard EIBEN a 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, s. 1-18. ISBN 978-3-95977-015-6. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ESA.2016.39. |
Další formáty:
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 a 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, s.~1-18. ISBN~978-3-95977-015-6. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ESA.2016.39.
|
