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(P-M) 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(P-M),
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 non-maximal
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) 413-422.
Selected papers that reference this paper
-
M. Pouzet, K. Reuter, I. Rival, and N. Zaguia,
A generalized permutahedron,
Algebra Universalis, 34 (1995) 496-509.
-
White, Dennis E. Sign-balanced posets.
J. Combin. Theory Ser. A 95 (2001), no. 1, 1-38.
[MR1840476 (2002e:05151),
05E10 (05A15 05E05 06A07)]
-
Il'yuta, G. G. A'Campo-Gusein-Zade diagrams as partially
ordered sets. (Russian) Izv. Ross. Akad. Nauk Ser. Mat. 65
(2001), no. 4, 49-66; translation in Izv. Math. 65 (2001),
no. 4, 687-704.
[MR1857710 (2002i:58052), 58K20 (06A06 16G20 58K40)]
Back to list of publications.