A loop-free algorithm for generating the linear extensions of a poset

DOI10.1007/BF01108590MaRDI QIDQ1917670zbMATH OpenFDO

Authors E. Rodney Canfield, S. Gill Williamson

Publication date 4 November 1996

Published in Order (Search for Journal in Brave)

zbMATH Keywords

linear extension\(\#P\)-completeloop-free algorithmposet-extension

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Generating Linear Extensions Fast
• Loopless generation of linear extensions of a poset
• Counting linear extensions

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1792682 (Why is no real title available?)
• scientific article; zbMATH DE number 3407692 (Why is no real title available?)
• A Gray Code for the Ideals of a Forest Poset
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Combinatorial Gray Codes
• Counting linear extensions
• Generating Linear Extensions Fast
• Generation of Permutations by Adjacent Transposition
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• On the translation of languages from left to right
• The complexity of computing the permanent

Cited in

(22)

• A loopless algorithm for generating the permutations of a multiset
• Generating the Linear Extensions of Certain Posets by Transpositions
• Cool-lex order and k-ary Catalan structures
• Binary bubble languages and cool-lex order
• scientific article; zbMATH DE number 6806844 (Why is no real title available?)
• scientific article; zbMATH DE number 5230562 (Why is no real title available?)
• On the random generation and counting of weak order extensions of a poset with given class cardinalities
• Counting linear extensions
• Effective Poset Inequalities
• scientific article; zbMATH DE number 16221 (Why is no real title available?)
• FUSING LOOPLESS ALGORITHMS FOR COMBINATORIAL GENERATION
• Counting linear extensions of restricted posets
• Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
• Mining posets from linear orders.
• Computing linear extensions for polynomial posets subject to algebraic constraints
• A loopless algorithm for generation of basic minimal interval orders
• Generating Gray codes for weak orders in constant amortized time
• Loopless generation of linear extensions of a poset
• A faster tree-decomposition based algorithm for counting linear extensions
• scientific article; zbMATH DE number 65462 (Why is no real title available?)
• Fundamentals of Computation Theory
• Efficient Algorithms for Listing Combinatorial Structures

This page was built for publication: A loop-free algorithm for generating the linear extensions of a poset

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