Counting linear extensions: parameterizations by treewidth

DOI10.1007/S00453-018-0496-4MaRDI QIDQ1739113zbMATH OpenOpenAlexWikidataFDO

Authors Xianqiang Yang

Publication date 25 April 2019

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-018-0496-4

zbMATH Keywords

treewidthparameterized complexitystructural parameterspartially ordered setslinear extensions

Mathematics Subject Classification ID

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

Recommendations

• Counting linear extensions: parameterizations by treewidth
• A faster tree-decomposition based algorithm for counting linear extensions
• A faster tree-decomposition based algorithm for counting linear extensions
• Counting linear extensions of restricted posets
• Counting linear extensions

Cites work

• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• scientific article; zbMATH DE number 5043346 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Convex rank tests and semigraphoids
• Cover-incomparability graphs of posets
• Easy problems for tree-decomposable graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Faster random generation of linear extensions
• Fundamentals of parameterized complexity
• Graph theory
• Linear extensions of N-free orders.
• Model counting for CNF formulas of bounded modular treewidth
• New results in minimum-comparison sorting
• On computing the number of linear extensions of a tree
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• On the complexity of some colorful problems parameterized by treewidth
• Parameterized algorithms
• Probabilistic preference logic networks
• The Parameterized Complexity of Counting Problems
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Treewidth. Computations and approximations

Cited in

(10)

• Grundy Distinguishes Treewidth from Pathwidth
• Counting linear extensions
• Counting linear extensions: parameterizations by treewidth
• Counting linear extensions of restricted posets
• Width notions for ordering-related problems
• Grundy distinguishes treewidth from pathwidth
• Counting Cherry reduction sequences in phylogenetic tree-child networks is counting linear extensions
• A faster tree-decomposition based algorithm for counting linear extensions
• A faster tree-decomposition based algorithm for counting linear extensions
• Using TPA to count linear extensions

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

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