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 |
Total number of downloads: Loading...
Files | Size | Format | View |
---|---|---|---|
Eiben2019_Artic ... LinearExtensionsParame.pdf | 519.8Kb |
View/ |