Scientific objectives and specific research themes

The research proposed under this project focuses on the development of efficient combinatorial algorithms and on the investigation of discrete structures of intrinsic interest, with the global aim of giving support of fundamental nature to computer science (CS).

This project's approach is of a classical nature. Of the multiple fronts of CS that try to give support to computationally intense research projects of modern science, this project falls into the mathematical category, attacking algorithmic problems rigorously. The algorithms that are developed are analysed for correctness and computational complexity, and, when, relevant, they are implemented.

The main themes that will be considered are the following:

1. Several approaches to the development of algorithms for combinatorial optimization problem;
2. Combinatorial problems from computational biology;
3. The structure of graphs and related objects;
4. Asymptotic properties of combinatorial structures.

Theme 1 will be coordinated by Yoshiko Wakabayashi (DCC-IME-USP), theme 2 by Carlos Eduardo Ferreira (DCC-IME-USP), theme 3, by Cláudio Leonardo Lucchesi (IC-UNICAMP) and theme 4 by Yoshiharu Kohayakawa (DCC-IME-USP).