Dentro da pesquisa relativa ao Problema 1, Investigações de problemas estruturais e algorítmicos em grafos, um dos objetivos primordiais na linha estrutural é o estudo de grafos perfeitos, grafos de intersecção, emparelhamentos, circuitos, caminhos, cortes e coloração de grafos.
O estudo de grafos perfeitos tem como objetivo principal dar continuidade a alguns resultados já obtidos por membros do grupo, tais como: algoritmo polinomial para testar a existência de circuitos pares induzidos em grafos planares e algoritmos de coloração para várias famílias de grafos perfeitos. Classes especiais de grafos perfeitos, como grafos de comparabilidade e grafos de intervalo, também serão estudados. No primeiro caso, objetivamos encontrar caracterizações de subclasses da classe dos grafos de comparabilidade através da relação com o seu grafo clique. Grafos clique, por sua vez, constituem uma classe especial de grafos de intersecção, sobre os quais temos interesse em aspectos relativos à caracterização, determinação do número de estabilidade e do número cromático--problemas esses ainda não resolvidos de forma satisfatória para esta classe de grafos. Esperamos que, para algumas subclasses dos grafos clique, possamos resolver esses problemas e encontrar um algoritmo de reconhecimento eficiente. Alguns resultados nesta direção foram obtidos para a classe dos grafos clique-completos (cf. [54, 59]).
A classe dos grafos de intervalo será objeto de nossos estudos, pois apesar de pesquisas recentes terem conduzido a diversos algoritmos ótimos ou quase ótimos [48, 64, 72] para o reconhecimento de tal classe, ainda persiste a pergunta que pretendemos responder: será que não existe um algoritmo ótimo mais simples e elegante para o reconhecimento dessa classe?
Quanto aos emparelhamentos em grafos, neste projeto pretendemos investigar a possibilidade de obter implementações paralelas que resolvam o problema do emparelhamento não ponderado e que atinjam acelerações significativas em relação a uma boa implementação seqüencial. Pretendemos realizar nossa implementação numa máquina de memória compartilhada de poucos processadores (SparcServer 1000, 8 processadores), e obter uma curva de performance com número de processadores variando de 2 a 8.
Uma área de interesse teórico em colorações de grafos é a das equações de Birkhoff-Lewis. Num trabalho recente de Dahab [17] é apresentada uma solução preliminar para as equações de Birkhoff-Lewis. A solução dessas equações revela a presença de uma forma dos importantes polinômios de Tchebyshev. Neste projeto objetivamos encontrar uma solução mais simples. Também estudaremos as conseqüências de tal solução e sua relevância para as áreas de mecânica quântica e teoria dos nós.
A pesquisa sobre tópicos relativos a circuitos e caminhos com comprimentos de paridade pré-fixada (ou não) considera aspectos relativos à existência, busca simples, e busca de uma tal estrutura com comprimento mínimo. Aqui o objetivo é investigar a complexidade computacional de tais problemas e desenvolver algoritmos eficientes, quando possível. Alguns resultados foram obtidos quanto à complexidade de certos problemas, bem como o desenvolvimento de algoritmos para alguns deles (Benatti, Hashimoto, e Wakabayashi [10], Porto [63]).
Os problemas relativos a cortes e transversais em grafos em que temos interesse consistem na determinação algorítmica de cortes mínimos, transversais mínimas, coleções disjuntas máximas de cortes, e coleções disjuntas máximas de transversais em vários tipos de grafos [19]. Um problema clássico desta natureza pede a determinação de uma transversal mínima dos cortes orientados de um grafo, que é resolvido pelo algoritmo de Lucchesi-Younger [55]. O problema dual, de determinar uma coleção disjunta máxima de transversais de cortes orientados, continua aberto [20, 69, 56]. Conjectura-se [77] que uma coleção disjunta máxima tem a mesma cardinalidade que um corte mínimo. Este problema continuará sendo investigado neste projeto.
No tocante aos métodos poliedrais, pesquisa prevista sob a designação de Problema 2, Estudo de métodos poliedrais e multi-algorítmicos para problemas combinatórios NP -difíceis, é nosso objetivo desenvolver algoritmos baseados na estratégia branch and cut para alguns problemas difíceis de otimização combinatória (por exemplo, o Problema da Pré-ordem Completa, o Problema da Ordem Parcial, o Problema da Pré-ordem, e o Problema da Partição de Grafos e Hipergrafos). A literatura nessa área teve um crescimento bastante grande nos últimos tempos, o que espelha a nossa tentativa de nos mantermos na ponta da pesquisa científica mundial. Para isso, o estudo da estrutura facial dos poliedros associados aos problemas que investigaremos é fundamental. Especificamente, o estudo da complexidade teórica bem como a busca de algoritmos heurísticos eficientes para os problemas da separação relativos a tais poliedros constituem objetivos principais desse trabalho.
Quanto ao uso de métodos multi-algorítmicos, a pesquisa será centrada em torno da técnica chamada Time Assíncrono. Esta técnica consiste na utilização de cada algoritmo disponível como sendo um agente autônomo compondo uma organização. Além dos agentes, esta organização possui uma ou mais memórias compartilhadas através das quais os agentes (algoritmos) podem trocar dados. Considerando que a utilização desta técnica se mostrou adequada para o Problema do Caixeiro Viajante, pretendemos fazer uso desta técnica em outros problemas combinatórios (como, por exemplo, roteamento de veículos e escalonamento de tarefas).
Quanto aos Problemas de Empacotamento, temos interesse primordial no caso tridimensional. É nosso objetivo desenvolver algoritmos com melhores desempenhos assintóticos do que os sugeridos na literatura, contribuindo dessa maneira com novas técnicas e novos limites. Também pretendemos implementar os algoritmos que serão desenvolvidos.
Dentro de nossas investigações de métodos probabilísticos sob o Problema 3, Investigações de aplicações de métodos probabilísticos em combinatória e em teoria da computação, o nosso objetivo é continuar os nossos estudos sobre grafos aleatórios, sobre problemas tipo Turán e Ramsey, e sobre algoritmos aleatórios e complexidade aleatória. Acreditamos que o nosso sucesso até o momento é uma indicação de que as nossas várias técnicas são promissoras (cf. Item 3).
Citamos apenas três problemas mais específicos que serão objeto de
atenção imediata. O primeiro deles concerne à busca de um resultado
geral para o problema extremal tipo Turán em grafos
aleatórios--aqui temos em mente um resultado como o de Rödl e
Rucinski [65, 66]. Os resultados em Haxell, Kohayakawa, e 
uczak [38, 39] mostram que este é um problema promissor.
O segundo problema que mencionamos versa sobre grafos minimais com a
propriedade de Ramsey induzida para um dado grafo arbitrário H: o
objetivo é estimar o tamanho de tal grafo em função de H. Este
problema para circuitos foi resolvido em Haxell, Kohayakawa, e 
uczak [37], e para árvores (versão não-induzida) foi
essencialmente resolvido em Haxell e Kohayakawa [36]. Conjecturas
específicas encontram-se em Graham e Rödl [26]. Finalmente,
citamos o problema de decidir se existe para todo grafo H um
grafo 
`esparso' (em um sentido preciso) que tem a propriedade
anti-Ramsey para H. Este problema, devido a Rödl e Tuza, foi
resolvido para circuitos por Haxell e Kohayakawa [35] e
Kohayakawa e 
uczak [46]. A investigação destes problemas é um
projeto conjunto com Haxell, 
uczak, e Rödl.