A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorKangas, Kustaa
dc.contributor.authorKoivisto, Mikko
dc.contributor.authorSalonen, Sami
dc.contributor.departmentDepartment of Computer Science
dc.contributor.departmentUniversity of Helsinki
dc.date.accessioned2020-01-02T13:56:15Z
dc.date.available2020-01-02T13:56:15Z
dc.date.issued2020-08-01
dc.description.abstractWe 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.description.versionPeer revieweden
dc.format.mimetypeapplication/pdf
dc.identifier.citationKangas , 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-1en
dc.identifier.doi10.1007/s00453-019-00633-1
dc.identifier.issn0178-4617
dc.identifier.issn1432-0541
dc.identifier.otherPURE UUID: 3ad2a784-e533-4cf5-bea2-d07af2feb68e
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/3ad2a784-e533-4cf5-bea2-d07af2feb68e
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85074360704&partnerID=8YFLogxK
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/38651339/Kangas2019_Article_AFasterTree_DecompositionBased_1.pdf
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/41983
dc.identifier.urnURN:NBN:fi:aalto-202001021094
dc.language.isoenen
dc.publisherSpringer New York
dc.relation.ispartofseriesAlgorithmicaen
dc.rightsopenAccessen
dc.subject.keywordAlgorithm selection
dc.subject.keywordEmpirical hardness
dc.subject.keywordLinear extension
dc.subject.keywordMultiplication of polynomials
dc.subject.keywordTree decomposition
dc.titleA Faster Tree-Decomposition Based Algorithm for Counting Linear Extensionsen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
dc.type.versionpublishedVersion
Files