Learning Centre

A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Kangas, Kustaa
dc.contributor.author Koivisto, Mikko
dc.contributor.author Salonen, Sami
dc.date.accessioned 2020-01-02T13:56:15Z
dc.date.available 2020-01-02T13:56:15Z
dc.date.issued 2020-08-01
dc.identifier.citation Kangas , K , Koivisto , M & Salonen , S 2020 , ' A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ' , Algorithmica , vol. 82 , no. 8 , pp. 2156-2173 . https://doi.org/10.1007/s00453-019-00633-1 en
dc.identifier.issn 0178-4617
dc.identifier.issn 1432-0541
dc.identifier.other PURE UUID: 3ad2a784-e533-4cf5-bea2-d07af2feb68e
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/3ad2a784-e533-4cf5-bea2-d07af2feb68e
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85074360704&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/38651339/Kangas2019_Article_AFasterTree_DecompositionBased_1.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/41983
dc.description.abstract We investigate the problem of computing the number of linear extensions of a given n-element poset whose cover graph has treewidth t. We present an algorithm that runs in time O~ (nt + 3) for any constant t; the notation O~ hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters n and t alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data.Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition. en
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Springer New York
dc.relation.ispartofseries Algorithmica en
dc.rights openAccess en
dc.title A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.contributor.department University of Helsinki
dc.subject.keyword Algorithm selection
dc.subject.keyword Empirical hardness
dc.subject.keyword Linear extension
dc.subject.keyword Multiplication of polynomials
dc.subject.keyword Tree decomposition
dc.identifier.urn URN:NBN:fi:aalto-202001021094
dc.identifier.doi 10.1007/s00453-019-00633-1
dc.type.version publishedVersion

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication