Counting Linear Extensions : Parameterizations by Treewidth
Permalink
Citation
Eiben , E , Ganian , R , Kangas , K & Ordyniak , S 2019 , ' Counting Linear Extensions : Parameterizations by Treewidth ' , Algorithmica , vol. 81 , no. 4 , pp. 1657-1683 . https://doi.org/10.1007/s00453-018-0496-4
| Title: | Counting Linear Extensions : Parameterizations by Treewidth |
| Author: | Eiben, E.; Ganian, R.; Kangas, K.; Ordyniak, S. |
| Contributor: | University of Helsinki, Department of Computer Science |
| Date: | 2019-04 |
| Language: | eng |
| Number of pages: | 27 |
| Belongs to series: | Algorithmica |
| ISSN: | 0178-4617 |
| URI: | http://hdl.handle.net/10138/303491 |
| Abstract: | We consider the #P-complete problem of counting the number of linear extensions of a poset (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 |
| Subject: |
Partially ordered sets
Linear extensions Parameterized complexity Structural parameters Treewidth 113 Computer and information sciences |
| Rights: |
Files in this item
Total number of downloads: Loading...
| Files | Size | Format | View |
|---|---|---|---|
| Eiben2019_Artic ... LinearExtensionsParame.pdf | 519.8Kb |
View/ |
This item appears in the following Collection(s)
-
Articles from TUHAT CRIS [38579]