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 organization: | Department of Computer Science Helsinki Institute for Information Technology |
| Date: | 2019-04 |
| Language: | eng |
| Number of pages: | 27 |
| Belongs to series: | Algorithmica |
| ISSN: | 0178-4617 |
| DOI: | https://doi.org/10.1007/s00453-018-0496-4 |
| 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 |
| Peer reviewed: | Yes |
| Rights: | cc_by |
| Usage restriction: | openAccess |
| Self-archived version: | publishedVersion |
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 [46493]