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

DOI10.1007/BF01108590zbMath0849.06003MaRDI QIDQ1917670

S. Gill Williamson, E. Rodney Canfield

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)

Related Items (7)

A loopless algorithm for generating the permutations of a multiset ⋮ Cool-lex order and \(k\)-ary Catalan structures ⋮ Effective Poset Inequalities ⋮ Binary bubble languages and cool-lex order ⋮ Generating Gray codes for weak orders in constant amortized time ⋮ FUSING LOOPLESS ALGORITHMS FOR COMBINATORIAL GENERATION ⋮ MINING POSETS FROM LINEAR ORDERS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Counting linear extensions
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• A Gray Code for the Ideals of a Forest Poset
• Combinatorial Gray Codes
• Generating Linear Extensions Fast
• On the translation of languages from left to right
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• Generation of Permutations by Adjacent Transposition

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