An improved algorithm to enumerate all traces that sort a signed permutation by reversals

International audienceIn 2008, Braga et al. proposed an algorithm to perform the enumeration of traces that sort a signed permutation by reversals. This algorithm has exponential complexity in both time and space. The original implementation uses a special structure, to handle the information during the process. However, even with this structure, memory consumption is still a problem. In this work, we propose a stack structure to represent the set of traces that is being enumerated by the algorithm. This new structure consumes less memory and can be kept in the main memory, improving the space and time performance of the algorithm