Counting Linear Extensions

Parameterizations by Treewidth

E. Eiben, R. Ganian, K. Kangas, S. Ordyniak

Tutkimustuotos: ArtikkelijulkaisuArtikkeliTieteellinenvertaisarvioitu

Kuvaus

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
Alkuperäiskielienglanti
LehtiAlgorithmica
Vuosikerta81
Numero4
Sivut1657-1683
Sivumäärä27
ISSN0178-4617
DOI - pysyväislinkit
TilaJulkaistu - huhtikuuta 2019
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä, vertaisarvioitu

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Lainaa tätä

Eiben, E., Ganian, R., Kangas, K., & Ordyniak, S. (2019). Counting Linear Extensions: Parameterizations by Treewidth. Algorithmica, 81(4), 1657-1683. https://doi.org/10.1007/s00453-018-0496-4
Eiben, E. ; Ganian, R. ; Kangas, K. ; Ordyniak, S. / Counting Linear Extensions : Parameterizations by Treewidth. Julkaisussa: Algorithmica. 2019 ; Vuosikerta 81, Nro 4. Sivut 1657-1683.
@article{857dfdf5eb35438586e427f338d00069,
title = "Counting Linear Extensions: Parameterizations by Treewidth",
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",
keywords = "Partially ordered sets, Linear extensions, Parameterized complexity, Structural parameters, Treewidth, 113 Computer and information sciences",
author = "E. Eiben and R. Ganian and K. Kangas and S. Ordyniak",
year = "2019",
month = "4",
doi = "10.1007/s00453-018-0496-4",
language = "English",
volume = "81",
pages = "1657--1683",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "4",

}

Eiben, E, Ganian, R, Kangas, K & Ordyniak, S 2019, 'Counting Linear Extensions: Parameterizations by Treewidth', Algorithmica, Vuosikerta 81, Nro 4, Sivut 1657-1683. https://doi.org/10.1007/s00453-018-0496-4

Counting Linear Extensions : Parameterizations by Treewidth. / Eiben, E.; Ganian, R.; Kangas, K.; Ordyniak, S.

julkaisussa: Algorithmica, Vuosikerta 81, Nro 4, 04.2019, s. 1657-1683.

Tutkimustuotos: ArtikkelijulkaisuArtikkeliTieteellinenvertaisarvioitu

TY - JOUR

T1 - Counting Linear Extensions

T2 - Parameterizations by Treewidth

AU - Eiben, E.

AU - Ganian, R.

AU - Kangas, K.

AU - Ordyniak, S.

PY - 2019/4

Y1 - 2019/4

N2 - 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

AB - 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

KW - Partially ordered sets

KW - Linear extensions

KW - Parameterized complexity

KW - Structural parameters

KW - Treewidth

KW - 113 Computer and information sciences

U2 - 10.1007/s00453-018-0496-4

DO - 10.1007/s00453-018-0496-4

M3 - Article

VL - 81

SP - 1657

EP - 1683

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -