A faster tree-decomposition based algorithm for counting linear extensions

DOI10.1007/S00453-019-00633-1MaRDI QIDQ786030zbMATH OpenOpenAlexWikidataFDO

Authors Kustaa Kangas, Mikko Koivisto, Sami Salonen

Publication date 12 August 2020

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-019-00633-1

zbMATH Keywords

algorithm selectiontree decompositionlinear extensionmultiplication of polynomialsempirical hardness

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorics of partially ordered sets (06A07)

Recommendations

• A faster tree-decomposition based algorithm for counting linear extensions
• scientific article; zbMATH DE number 16221
• scientific article; zbMATH DE number 4041286
• Counting linear extensions: parameterizations by treewidth
• Counting linear extensions: parameterizations by treewidth

Cites work

• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A faster tree-decomposition based algorithm for counting linear extensions
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Bucket elimination: A unifying framework for reasoning
• Complexity of Finding Embeddings in a k-Tree
• Contribution to nonserial dynamic programming
• Convex rank tests and semigraphoids
• Counting linear extensions
• Counting linear extensions: parameterizations by treewidth
• Dynamic programming meets the principle of inclusion and exclusion
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Empirical hardness models, methodology and a case study on combinatorial auctions
• Fast Library for Number Theory: An Introduction
• Faster integer multiplication
• Improving the efficiency of dynamic programming on tree decompositions via machine learning
• New results in minimum-comparison sorting
• On computing the number of linear extensions of a tree
• On the bit-complexity of sparse polynomial and series multiplication
• Optimal partial-order plan relaxation via MaxSAT
• Probabilistic preference logic networks
• Structure discovery in Bayesian networks by sampling partial orders
• The Transitive Reduction of a Directed Graph
• Tree decompositions with small cost
• Using TPA to count linear extensions

Cited in

(8)

• Fast Counting with Bounded Treewidth
• Generating Linear Extensions Fast
• A faster tree-decomposition based algorithm for counting linear extensions
• scientific article; zbMATH DE number 7666239 (Why is no real title available?)
• scientific article; zbMATH DE number 16221 (Why is no real title available?)
• Counting linear extensions: parameterizations by treewidth
• Counting linear extensions: parameterizations by treewidth
• Using TPA to count linear extensions

Describes a project that uses

Uses Software

• FLINT
• WEKA
• htd

This page was built for publication: A faster tree-decomposition based algorithm for counting linear extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786030)