Counting Linear Extensions: Parameterizations by Treewidth
- Submitting institution
-
The University of Sheffield
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 2510
- Type
- D - Journal article
- DOI
-
10.1007/s00453-018-0496-4
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 1657
- Volume
- 81
- Issue
- 4
- ISSN
- 0178-4617
- Open access status
- Compliant
- Month of publication
- September
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
3
- Research group(s)
-
A - Algorithms
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Counting the number of linear extensions of a poset (LE) is a fundamental problem in order theory with applications in sorting, sequence analysis, rank tests, preference reasoning, planning and graphical models. A major technical breakthrough of this paper is the introduction of novel techniques for showing hardness of counting problems, making it possible to resolve an open problem of Dagstuhl seminar 13331 and show that the best-known algorithm for learning Bayesian networks is optimal.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -