Constant delay Gray code enumeration of ideals and antichains in posets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911553171750912 |
|---|---|
| author | Brenner, Sofia Fink, Jiří |
| author_facet | Brenner, Sofia Fink, Jiří |
| contents | We present an algorithm that enumerates all ideals of an input poset with constant delay in Gray code order, i.e., such that consecutively visited ideals differ in at most three elements. This answers a long-standing open problem posed by Pruesse and Ruskey, and improves upon previous algorithms by Pruesse and Ruskey, Squire, Habib, Medina, Nourine and Steiner, as well as Abdo. Using the same techniques, we also obtain an algorithm that enumerates all antichains of an input poset with constant delay such that successively visited antichains differ in at most three elements.
As a key technical ingredient, we introduce a new potential-based analysis framework for recursive algorithms, which we call the Pyramid method. We show that this method subsumes the Push-out method of Uno. Beyond the present application, the Pyramid method is a general framework to analyze recursive algorithms and may thus be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_28118 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Constant delay Gray code enumeration of ideals and antichains in posets Brenner, Sofia Fink, Jiří Data Structures and Algorithms Discrete Mathematics We present an algorithm that enumerates all ideals of an input poset with constant delay in Gray code order, i.e., such that consecutively visited ideals differ in at most three elements. This answers a long-standing open problem posed by Pruesse and Ruskey, and improves upon previous algorithms by Pruesse and Ruskey, Squire, Habib, Medina, Nourine and Steiner, as well as Abdo. Using the same techniques, we also obtain an algorithm that enumerates all antichains of an input poset with constant delay such that successively visited antichains differ in at most three elements. As a key technical ingredient, we introduce a new potential-based analysis framework for recursive algorithms, which we call the Pyramid method. We show that this method subsumes the Push-out method of Uno. Beyond the present application, the Pyramid method is a general framework to analyze recursive algorithms and may thus be of independent interest. |
| title | Constant delay Gray code enumeration of ideals and antichains in posets |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2603.28118 |