Gray Codes for the Ideals of Interval Orders

✍ Scribed by Michel Habib; Lhouari Nourine; George Steiner

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 218 KB
• Volume: 25
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0863

✦ Synopsis

The generation of combinatorial objects in a Gray code manner means that the difference between successive objects is small, e.g., one element for subsets or one transposition for permutations of a set. The existence of such Gray codes is often equivalent to an appropriately defined graph on these objects being Hamiltonian. We show that if the graph G is the covering graph of the lattice of the order ideals of an interval order, then G 2 has a Hamiltonian path. This leads to an algorithm to generate the ideals of interval orders in constant time per ideal. We also prove that the subgraph of G 2 induced by the ideals of any fixed cardinality also has a Hamiltonian path. This proves a conjecture of Pruesse and Ruskey for interval orders. We also show how these paths can be combined into a layered Hamiltonian path of G 2 , yielding a Gray code on the ideals in nondecreasing order of their cardinalities.