A faster tree-decomposition based algorithm for counting linear extensions
From MaRDI portal
Publication:786030
DOI10.1007/s00453-019-00633-1zbMath1452.68265OpenAlexW2960650218WikidataQ127173469 ScholiaQ127173469MaRDI QIDQ786030
Kustaa Kangas, Sami Salonen, Mikko Koivisto
Publication date: 12 August 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-019-00633-1
tree decompositionalgorithm selectionlinear extensionmultiplication of polynomialsempirical hardness
Analysis of algorithms (68W40) Trees (05C05) Nonnumerical algorithms (68W05) Combinatorics of partially ordered sets (06A07)
Related Items (1)
Uses Software
Cites Work
- 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
- Counting linear extensions: parameterizations by treewidth
- 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
- Contribution to 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
- Faster Integer Multiplication
- 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
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
- 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
