Generating the Linear Extensions of Certain Posets by Transpositions

DOI10.1137/0404037zbMath0757.05075OpenAlexW1985733916MaRDI QIDQ3992179

Frank Ruskey, Gara Pruesse

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

posetHamiltonian graphtranspositionHamilton pathlinear extensionsaverage time algorithm

Mathematics Subject Classification ID

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

Related Items (14)

Generating linear extensions of posets by transpositions ⋮ A generalized permutahedron ⋮ Cool-lex order and \(k\)-ary Catalan structures ⋮ De Finetti lattices and magog triangles ⋮ Generating permutations with given ups and downs ⋮ Research problem: combinatorial and multilinear aspects of sign-balanced posets ⋮ \(N\)-free orders and minimal interval extensions ⋮ Unnamed Item ⋮ Sign-balanced posets ⋮ Generating alternating permutations lexicographically ⋮ Linear extension diameter of level induced subposets of the Boolean lattice ⋮ Gray code enumeration of families of integer partitions ⋮ Gray codes from antimatroids ⋮ MINING POSETS FROM LINEAR ORDERS

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