A Gray Code for the Ideals of Acyclic Posets
Gang Li, Department of Computer Science, University of Victoria.
(Enumerating Spider Squishings)
Frank Ruskey, Department of Computer Science, University of Victoria.
- These results were presented at the 26th South East Conference on
Combinatorics, Graph Theory, and Computing, 1995.
Here are some scans of the slides from that talk:
A six element fence poset and its ideal graph.
Spider = ayclic poset.
Spider for overlay.
Spider = ayclic poset OVERLAY. Missing is a shoe
overlay for showing some squishings (something like
Spider close-ups showing continued branching.
Parity difference is one of +1, 0, -1.
Definitions; e.g., q-code, squishings.
Allowed relations between q and r.
The path traced out by the proof and by the algorithm.
The relation between the proof and the algorithm.
Non-recursive look at the algorithm.
Second problem --- which ideal is first?
Final slide: Open Questions.
- Gang (Kenny) Li now works for i2 Technologies in Dallas, Texas.
- Donald Knuth liked the Gray code so much that he couldn't resist
developing his own implementation.
See his CWEB program
Back to list of publications.