Counting Linear Extensions : Parameterizations by Treewidth

Show full item record



Eiben , E , Ganian , R , Kangas , K & Ordyniak , S 2019 , ' Counting Linear Extensions : Parameterizations by Treewidth ' , Algorithmica , vol. 81 , no. 4 , pp. 1657-1683 .

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
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
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 PDF View/Open

This item appears in the following Collection(s)

Show full item record