Generating Linear Extensions of Certain Posets by Transpositions
Gara Pruesse,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
For poset P define the graph G(P) whose vertices are
the linear extensions of P and where two vertices are
connected by an edge if the corresponding linear extensions differ
by a transposition.
Let P be a poset and M a subset of its
maximal elements for which G(PM) has a
Hamilton path (cycle). If no element of P
has exactly one ancestor in M
then G(P) also has a Hamilton path (cycle).
Given only P and a constant average time algorithm
for building a path (cycle) in G(PM),
a Hamilton path (cycle)
can also be constructed in G(P) in
constant average time.
As an application of the results stated above it is proved that the
linear extensions of any ranked poset in which every nonmaximal
element has at least two (upper) covers can be generated by
transpositions in constant average time.
Notes

Appears in
SIAM J. Discrete Mathematics 4 (1991) 413422.
Selected papers that reference this paper

M. Pouzet, K. Reuter, I. Rival, and N. Zaguia,
A generalized permutahedron,
Algebra Universalis, 34 (1995) 496509.

White, Dennis E. Signbalanced posets.
J. Combin. Theory Ser. A 95 (2001), no. 1, 138.
[MR1840476 (2002e:05151),
05E10 (05A15 05E05 06A07)]

Il'yuta, G. G. A'CampoGuseinZade diagrams as partially
ordered sets. (Russian) Izv. Ross. Akad. Nauk Ser. Mat. 65
(2001), no. 4, 4966; translation in Izv. Math. 65 (2001),
no. 4, 687704.
[MR1857710 (2002i:58052), 58K20 (06A06 16G20 58K40)]
Back to list of publications.