A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

Show simple item record

dc.contributor University of Helsinki, Aalto University en
dc.contributor University of Helsinki, Department of Computer Science en
dc.contributor University of Helsinki, Department of Computer Science en
dc.contributor.author Kangas, Kustaa
dc.contributor.author Koivisto, Mikko
dc.contributor.author Salonen, Sami
dc.date.accessioned 2020-11-05T13:39:01Z
dc.date.available 2020-11-05T13:39:01Z
dc.date.issued 2019-10-03
dc.identifier.citation Kangas , K , Koivisto , M & Salonen , S 2019 , ' A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ' , Algorithmica , vol. 82 , pp. 2156-2173 . https://doi.org/10.1007/s00453-019-00633-1 en
dc.identifier.issn 1432-0541
dc.identifier.other PURE: 127371846
dc.identifier.other PURE UUID: 435f39bf-47cf-4883-b94f-caf56f87fc37
dc.identifier.other RIS: urn:B59D07B4061B2B7E089BD696AF49705F
dc.identifier.other RIS: Kangas2019
dc.identifier.other ORCID: /0000-0001-9662-3605/work/83052281
dc.identifier.other ORCID: /0000-0002-5262-7919/work/83052834
dc.identifier.other WOS: 000557558900003
dc.identifier.uri http://hdl.handle.net/10138/321138
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 $${\tilde{O}}(n^{t+3})$$O~(nt+3)for any constant t; the notation $${\tilde{O}}$$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.extent 18
dc.language.iso eng
dc.relation.ispartof Algorithmica
dc.rights en
dc.subject Algorithm selection en
dc.subject COMPLEXITY en
dc.subject Empirical hardness en
dc.subject FRAMEWORK en
dc.subject Linear extension en
dc.subject Multiplication of polynomials en
dc.subject Tree decomposition en
dc.subject 113 Computer and information sciences en
dc.subject 111 Mathematics en
dc.title A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions en
dc.type Article
dc.description.version Peer reviewed
dc.identifier.doi https://doi.org/10.1007/s00453-019-00633-1
dc.type.uri info:eu-repo/semantics/other
dc.type.uri info:eu-repo/semantics/publishedVersion
dc.contributor.pbl

Files in this item

Total number of downloads: Loading...

Files Size Format View
Kangas2020_Arti ... ree_DecompositionBased.pdf 349.2Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record