Generating Linear Extensions of Posets by Transpositions

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.


This paper considers the problem of listing all linear extensions of a partial order so that successive extensions differ by the transposition of a single pair of elements. A necessary condition is given for the case when the partial order is a forest. A necessary and sufficient condition is given for the case where the partial order consists of disjoint chains. Some open problems are mentioned.


Selected papers that reference this paper

Back to list of publications.