Projekt

For over 20 years, the most fundamental search algorithms in computer algebra have been built around partitions. Partitions only store the information whether or not two values of a set are in the same orbit under the permutation action of a particular group. This leads to search trees that are unnecessarily large, because redundant work is performed (potentially very often). In this project the usage of graphs instead of partitions as the fundamental data structure in search algorithms will be investigated. Graphs allow for much richer and more complex relations to be expressed. The method called 'pruning the search tree' has recently been massively improved by using orbital graphs for refining and pruning, after two decades where the state of the art had been practically unchanged. The authors believe that the key to even better performance is to replace partitions by graphs in search algorithms. However, it is not clear whether such a replacement is feasible based on the state of the art.

• Prof. Dr. Rebecca Waldecker

  Universität Halle-Wittenberg
  Institut für Mathematik
  Halle (Saale)