A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

Kustaa Kangas, Mikko Koivisto*, Sami Salonen

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

32 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
JulkaisuAlgorithmica
DOI - pysyväislinkit
TilaJulkaistu - 1 tammikuuta 2019
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki Sukella tutkimusaiheisiin 'A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä