Generating the Linear Extensions of Certain Posets by Transpositions

DOI10.1137/0404037MaRDI QIDQ3992179zbMATH OpenOpenAlexFDO

Authors Gara Pruesse, Frank Ruskey

Publication date 28 June 1992

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0404037

zbMATH Keywords

average time algorithmHamilton pathHamiltonian graphlinear extensionsposettransposition

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Total orders (06A05) Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains
• A loop-free algorithm for generating the linear extensions of a poset
• Generating Linear Extensions Fast
• Loopless generation of linear extensions of a poset
• scientific article; zbMATH DE number 65462

Cited in

(22)

• Generating permutations with given ups and downs
• \(N\)-free orders and minimal interval extensions
• Gray codes from antimatroids
• Generating linear extensions by adjacent transpositions
• On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains
• Gray code enumeration of families of integer partitions
• A generalized permutahedron
• Cool-lex order and k-ary Catalan structures
• De Finetti lattices and magog triangles
• Generating linear extensions of posets by transpositions
• Linear extension diameter of level induced subposets of the Boolean lattice
• Research problem: combinatorial and multilinear aspects of sign-balanced posets
• Linear extension diameter of subposets of Boolean lattice induced by two levels
• Mining posets from linear orders.
• scientific article; zbMATH DE number 4106894 (Why is no real title available?)
• Hamilton Paths in Graphs of Linear Extensions for Unions of Posets
• scientific article; zbMATH DE number 65462 (Why is no real title available?)
• The Graph of Linear Extensions Revisited
• Fundamentals of Computation Theory
• Generating alternating permutations lexicographically
• Sign-balanced posets
• Bender-Knuth involutions on linear extensions of posets

This page was built for publication: Generating the Linear Extensions of Certain Posets by Transpositions

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