A área de Combinatória e Grafos trata de abstrações de certos problemas práticos encontrados na indústria (projetos de chips VLSI, administração de frotas de veículos, sistemas operacionais de computadores, etc.) e em outras áreas da matemática e da pesquisa operacional. Muitos destes problemas podem ser descritos sobre um grafo. Os problemas consistem em encontrar uma configuração ótima (máxima ou mínima, conforme o caso) de um certo tipo no grafo. A dificuldade de todos os problemas de CG está em desenvolver algoritmos eficientes que encontrem a configuração ótima desejada. Para alguns dos problemas, algoritmos eficientes muito interessantes já foram descobertos, mas para muitos outros, a procura por algoritmos eficientes continua. Nosso grupo tem interesse não só nas técnicas mais tradicionais como também em algoritmos paralelos, algoritmos probabilísticos e algoritmos que buscam soluções "aproximadamente ótimas''. Suspeita-se que para muitos dos problemas não existem algoritmos eficientes. A fundamentação desta suspeita é fornecida pela Teoria da Complexidade Computacional. Uma pergunta básica desta Teoria é "Que tipos de problemas são intrinsecamente difíceis?'' Esta é uma questão fundamental que tem preocupado um grande número de pesquisadores nos últimos 20 anos.

Para obter maiores informações, envie uma mensagem para o Professor Yoshiharu Kohayakawa: yoshi(arroba)ime.usp.br 

Veja também Combinatória.