Collaborative Research Unit

Combinatorial algorithms and algorithmic graph theory

Acronym
CAAGT
Co-ordinator
Other information
Research disciplines
  • Natural sciences
    • Computer science
    • Combinatorics
    • Software engineering
    • Mathematical software
Description
"We study search and generation algorithms on combinatorial objects likegraphs, incidence geometries en subsets of these objects withinteresting combinatorial properties.Quite often these algorithms require a recursive traversal of atree-like search space using various pruning heuristics. Specificpruning methods exploit the inherent symmetries of the objects(automorphisms, equivalences, unique labelings) or are based onmathematical properties that are specific to the problem at hand.On the one hand we try to design, improve and study these combinatorialalgorithms, but on the other hand we also apply these algorithms to realmathematical problems, hoping to generate new mathematical results incombinatorial theory and combinatorial geometry in particular.We are also interested in other algorithmic aspects of graph theory. Wehave done research on optimal algoritms for data-exchange on networks ofparallel processors, efficient reduction of cubical Yutsis-graphs anddistance related properties of rotation graphs for binary couplingtrees.This research domain has applications in representation theory, morespecifically in finding optimal expressions for 3nj-coefficients, andalso in mathematical biology, in the computation of similarity measuresfor dendrograms."