A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
From MaRDI portal
Publication:5009467
DOI10.4230/LIPIcs.IPEC.2018.5OpenAlexW2920579836MaRDI QIDQ5009467
Mikko Koivisto, Sami Salonen, Kustaa Kangas
Publication date: 4 August 2021
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2019/10206/pdf/LIPIcs-IPEC-2018-5.pdf
tree decompositionalgorithm selectionlinear extensionmultiplication of polynomialsempirical hardness
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dynamic programming meets the principle of inclusion and exclusion
- Counting linear extensions
- On computing the number of linear extensions of a tree
- Using TPA to count linear extensions
- Tree decompositions with small cost
- New results in minimum-comparison sorting
- On the bit-complexity of sparse polynomial and series multiplication
- Bucket elimination: A unifying framework for reasoning
- Nonserial dynamic programming
- Optimal Partial-Order Plan Relaxation via MaxSAT
- Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning
- Empirical hardness models
- Convex Rank Tests and Semigraphoids
- Complexity of Finding Embeddings in a k-Tree
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Counting Linear Extensions: Parameterizations by Treewidth
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- The Transitive Reduction of a Directed Graph
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Fast Library for Number Theory: An Introduction
This page was built for publication: A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
