Counting linear extensions: parameterizations by treewidth

DOI10.1007/s00453-018-0496-4zbMath1421.68074OpenAlexW2891118272WikidataQ90101878 ScholiaQ90101878MaRDI QIDQ1739113

Xianqiang Yang

Publication date: 25 April 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0496-4

zbMATH Keywords

treewidthpartially ordered setsparameterized complexitylinear extensionsstructural parameters

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Total orders (06A05)

Related Items (3)

Grundy Distinguishes Treewidth from Pathwidth ⋮ Unnamed Item ⋮ A faster tree-decomposition based algorithm for counting linear extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Model counting for CNF formulas of bounded modular treewidth
• Fundamentals of parameterized complexity
• On the complexity of some colorful problems parameterized by treewidth
• Cover-incomparability graphs of posets
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Faster random generation of linear extensions
• On computing the number of linear extensions of a tree
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Treewidth. Computations and approximations
• New results in minimum-comparison sorting
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Linear extensions of N-free orders.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph Theory
• Easy problems for tree-decomposable graphs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Convex Rank Tests and Semigraphoids
• A random polynomial-time algorithm for approximating the volume of convex bodies
• The Parameterized Complexity of Counting Problems
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Counting linear extensions: parameterizations by treewidth