A parallel algorithm for the enumeration of Costas sequences
Óscar Moreno, Pei Pei, John G. Ramirez · PPSC · 1995
Costas sequences are special permutations which are important in sonar and radar applications. Common backtracking algorithms add terms to a single side of the sequence, but we have developed an algorithm that enumerates all Costas sequences more efficiently by performing backtracking adding terms to both sides of the sequence. This novel technique is combined with the fact that Costas sequences are invariant under the symmetries of the rectangle to reduce efficiently the computation time by not repeating a searched pattern as subpattern in a different branch of the search. We have adapted this method for its implementation on parallel MIMD computers by the use of the manager-worker technique obtaining almost perfect efficiency on the time distribution.