Generating the Linear Extensions of Certain Posets by Transpositions
Gara Pruesse, Frank Ruskey · SIAM Journal on Discrete Mathematics · 1991
For poset $\mathcal{P}$ define the graph $G( \mathcal{P} )$ whose vertices are the linear extensions of $\mathcal{P}$ and where two vertices are connected by an edge if the corresponding linear extensions differ by a transposition. Let $\mathcal{P}$ be a poset and M a subset of its minimal elements for which $G( \mathcal{P} - M )$ has a Hamilton path (cycle). If no element of $\mathcal{P} - M$ has exactly one descendant in M then $G( \mathcal{P} )$ also has a Hamilton path (cycle). Given only $\mathcal{P}$ and a constant average time algorithm for building a path (cycle) in $G( \mathcal{P} - M )$, a Hamilton path (cycle) can also be constructed in $G( \mathcal{P} )$ in constant average time. As an application of the results stated above it is proved that the linear extensions of any ranked poser in which every nonmaximal element has at least two (upper) covers can be generated by transpositions in constant average time.