☆

1

How to efficiently generate combinatorial structures
such as posets, trees, B-trees, graphs, permutations, set partitions, Dyck paths, multisets or necklaces ... ?
The Ruskey's book gives answers.
It contains many surprising descriptions (and bibliographic references)
of constant amortized time (CAT) and loopless algorithms.
> **CAT Algorithms** The holy grail of generating combinatorial objects is to find an algorithm that runs in Constant Amortized Time. This means that the amount of computation, after a small amount of preprocessing, is proportional to the number of objects that are listed. We do not count the time to actually output or process the objects; we are only concerned with the amount of data structure change that occurs as the objects are being generated.
_ Ruskey's book, page 8 _
> ** Loopless algorithm ** is an imperative algorithm that generates successive combinatorial objects, such as partitions, permutations, and combinations, in constant time and the first object in linear time
_ https://en.wikipedia.org/wiki/Loopless_algorithm _

☆

1

Nice paper!
- Publicly available implementation: https://gitlab.inria.fr/bora-ucar/karp--sipser-reduction
- I like Theorem 3.1 a lot! I'm thinking how to generalize it, adapt it, use it for other problems.
- Would have liked to see experiments on larger graphs.
- Is there any other Rules that could be considered in addition to Rules 1 and 2?

## Comments: