Counting Linear Extensions : Parameterizations by Treewidth

Show full item record



Permalink

http://hdl.handle.net/10138/303491

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

This item appears in the following Collection(s)

Show full item record