Back to Search
Start Over
A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
- Source :
- Algorithmica. 82:2156-2173
- Publication Year :
- 2019
- Publisher :
- Springer Science and Business Media LLC, 2019.
-
Abstract
- We investigate the problem of computing the number of linear extensions of a givenn-element poset whose cover graph has treewidtht. We present an algorithm that runs in time$${\tilde{O}}(n^{t+3})$$O~(nt+3)for any constantt; 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 parametersnandtalone: 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.
- Subjects :
- Multivariate polynomial
General Computer Science
0102 computer and information sciences
02 engineering and technology
Running time
Trees (mathematics)
01 natural sciences
Tilde
Algorithm selection
Cover graph
Linear extensions
Linear extension
111 Mathematics
Parameter estimation
0202 electrical engineering, electronic engineering, information engineering
Empirical hardness
Multiplication of polynomials
Exclusion algorithms
Mathematics
COMPLEXITY
000 Computer science, knowledge, general works
Counting linear extensions
Estimation theory
Applied Mathematics
Tree decomposition
FRAMEWORK
113 Computer and information sciences
Fast multiplication
Computer Science Applications
Dynamic programming
Treewidth
010201 computation theory & mathematics
Computer Science
Theory of computation
020201 artificial intelligence & image processing
Partially ordered set
Algorithm
Subjects
Details
- ISSN :
- 14320541 and 01784617
- Volume :
- 82
- Database :
- OpenAIRE
- Journal :
- Algorithmica
- Accession number :
- edsair.doi.dedup.....3abf092b8c2e92c09d1f8a1295d9dd4f