A Gray code for the ideals of a forest poset. (English) Zbl 0782.94014

Koda, Yasunori; Ruskey, Frank

J. Algorithms 15, No. 2, 324-340 (1993).

Summary: We present two algorithms for listing all ideals of a forest poset. These algorithms generate ideals in Gray code manner; that is, consecutive ideals differ by exactly one element. Both algorithms use storage \(O(n)\), where \(n\) is the number of elements in the poset. On each iteration, the first algorithm does a partial traversal of the current ideal being listed and runs in time \(O(nN)\), where \(N\) is the number of ideals of the poset. The second algorithm mimics the first, but eliminates the traversal and runs in time \(O(N)\). This algorithm has the property that the amount of computation between successive ideals is \(O(1)\); such algorithms are said to be loopless.

MSC:

94B15	Cyclic codes
06A07	Combinatorics of partially ordered sets

Keywords:

Hamiltonian path; poset; Gray code; ideals; loopless