An improved algorithm to enumerate all traces that sort a signed permutation by reversals - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

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

(1) , (2)
1
2

Abstract

In 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.
Not file

Dates and versions

hal-00748579 , version 1 (05-11-2012)

Identifiers

Cite

Christian Baudet, Zanoni Dias. An improved algorithm to enumerate all traces that sort a signed permutation by reversals. ACM Symposium on Applied Computing (SAC), Mar 2010, Sierre, Switzerland. pp.1521-1525, ⟨10.1145/1774088.1774416⟩. ⟨hal-00748579⟩
82 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More