COMPLEXIDADE DE ESTRUTURAS DISCRETAS

Y. KOHAYAKAWA

Resumo. Apresentamos neste relatório as atividades de formação de recursos humanos de nossa equipe no período de fevereiro de 1999 a fevereiro de 2000.

Formação de Recursos Humanos

Doutorado

Concluídos

1. Maria Emília Machado Telles Walter [J. Meidanis/IC-UNICAMP]. Bolsa da capes. Título da tese: Algoritmos para Problemas em Rearranjo de Genomas. Término: novembro/99.

2. Orlando Lee [Y. Wakabayashi/IME-USP]. Título da tese: Coberturas por Circuitos em Grafos Mistos. Bolsa da capes. Término: dezembro/99.

3. Bráulio Maia Junior [M. Lemos/DM-UFPE]. Título da tese: Matróides Co-

nexas com Circunferência Pequena. Bolsa da capes. Término: dezembro/99. Em andamento

1. Nalvo Franco de Almeida Jr [J.C. Setubal/IC-Unicamp]. Título da tese: Ferramentas computacionais para genômica . Bolsa PICD-capes com sanduíche capes-Fulbright. Ingresso no programa: março/95. Defesa prevista para 2000.

2. Júlio César Lopez Hernandez [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Análise e Implementação de Algoritmos Criptográficos baseados em Curvas Elípticas. Sem bolsa no momento. Ingresso no programa: agosto/95. Defesa prevista para abril/2000.

3. José Roberto Monteiro [Cláudio L. Lucchesi e (co-orientador) Ricardo Dahab/IC-UNICAMP]. Título do projeto: Protocolos Criptográficos Eficientes para Troca Autenticada. Sem bolsa no momento). Ingresso no programa: março/95. Defesa prevista para agosto/2000.

4. Jair Donadelli Júnior [Y. Kohayakawa/IME-USP]. Título do projeto: Métodos Probabilísticos e Métodos Topológicos em Combinatória Extremal. Bolsa da capes até dezembro/97 e bolsa do cnpq desde janeiro/98. Ingresso no programa: março/96.

5. Estela Maris Rodrigues [Y. Wakabayashi/IME-USP]. Título do projeto: Algoritmos de Inferência Filogenética. Bolsa do cnpq. Ingresso no programa: março/97.

6. Guilherme Pimentel Telles [J. Meidanis/IC-UNICAMP]. Título do projeto: Mapas Físicos de DNA. Bolsa da fapesp. Ingresso no programa: março/97.

7. Christiane Neme Campos Toledo [Cláudio L. Lucchesi/ IC-UNICAMP]. Título do projeto: Grafos Cobertos por Emparelhamentos. Bolsa do cnpq. Ingresso no programa: março/97.

Data: 29 de fevereiro de 2000. Projeto no. 107/97.

8. Liliane Rose Benning Salgado [Y. Wakabayashi/IME-USP]. Título do projeto: Aproximabilidade de Problemas de Otimização em Grafos. Bolsa da fapesp desde agosto/98. Ingresso no programa: março/98.

9. Zanoni Dias [J. Meidanis/IC-UNICAMP]. Título do projeto: Rearranjo de Genomas. Bolsa da fapesp. Ingresso no programa: março/98.

10. Marco Aurélio Stefanes [J. Soares/IME-USP]. Título do projeto: Algoritmos Paralelos para Grafos e Geometria Computacional. Bolsa da fapesp desde agosto/98. Ingresso no programa: março/98.

11. Francisco Elói Soares de Araújo [J. Soares/IME-USP]. Título do projeto: Biologia Computacional. Ingresso no programa: agosto/98.

12. Glauber Ferreira Cintra [Y. Wakabayashi/IME-USP]. Título do projeto: Algoritmos para Problemas de Corte Multidimensionais. Ingresso no programa: agosto/98.

13. Emerson Alexandre de Oliveira Lima [S. Lins/DM-UFPE]. Título do projeto: Implementação de uma Dinâmica Combinatória para Classificar 3-variedades. Ingresso no programa: março/99.

14. Simone Dantas de Souza [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Título do projeto: Problemas-sanduíche em Grafos. Bolsa da capes. Ingresso no programa: março/99.

15. Alexandre Melo Braga [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Segurança de Sistemas Móveis. Bolsa do cnpq. Ingresso no programa: agosto/99.

16. Lucas de Carvalho Ferreira [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Métodos Formais em Protocolos Criptográficos. Sem bolsa–com vínculo empregatício em outra instituição. Ingresso no programa: agosto/99.

17. Loana Tito Nogueira [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Complexidade de Problemas de Partição em Grafos. Bolsa do cnpq. Ingresso no programa: outubro/99.

Mestrado

Concluídos

1. Glauber Ferreira Cintra [Y. Wakabayashi/IME-USP]. Bolsa do cnpq. Título da dissertação: Algoritmos Híbridos para Problemas de Corte Unidimensional. Término: julho/98. 1o. Prêmio no VI Concurso CLEI-UNESCO de Teses de Mestrado, 1999.

2. Márcia Graci Carneiro de Oliveira [M. Lemos/DM-UFPE]. Bolsa do cnpq. Título da dissertação: Decomposição de Grafos Planares em Ciclos Pares. Término: maio/99.

3. Ivan da Silva Sendim [Ricardo Dahab/IC-UNICAMP]. Título da dissertação: Funções de Hashing para Aplicações Criptográficas. Bolsa da capes. Término: julho/99.

4. Alexandre Melo Braga [Ricardo Dahab e Cecília M. F. Rubira/ IC-UNICAMP]. Título da dissertação: Análise Comparativa e Proposta de Extensão à Arquitetura Criptográfica JAVA. Bolsa do cnpqe posteriormente fapesp. Término: agosto/99.

5. Loana Tito Nogueira [S. Klein/IM-COPPE-UFRJ]. Bolsa da capes. Título da dissertação: Grafos Split e Grafos Split Generalizados. Término: setembro/99.

6. Ricardo Scachetti Pereira [Cid de Carvalho de Souza/IC-UNICAMP]. Algoritmos Exatos e Heurísticas para Problemas de Otimização Combinatória encontrados na Logística de Distribuição de Revistas. Bolsa da fapesp. Início: agosto/96. Término: setembro/99.

7. Andrea Rosario Pari Soto [S. Klein/IM-COPPE-UFRJ e N. Maculan/COPPE-UFRJ]. Bolsa da capes. Título da dissertação: Algoritmos Aproximativos para o Problema do Caixeiro Viajante. Término: outubro/99.

8. Alexandre Scalzitti [Y. Kohayakawa/IME-USP]. Título da dissertação: Convergência na Teoria dos Grafos Aleatórios. Término: outubro/99.

9. Mário Leston Rey [P. Feofiloff/IME-USP]. Título da dissertação: T -junções, T -cortes e funções conservativas. Bolsa do cnpq. Término: novembro/99.

10. Edésio R. Sibrão [C.E. Ferreira/IME-USP]. Título do projeto: Escalonamento em Sistemas de Produção: um Estudo de Caso. Bolsa da capes de agosto/96 até julho/98. Ingresso no programa: agosto/96. Término: dezembro/99.

11. Carlos R. Pantaleon Dionisio [J.C. de Pina/IME-USP]. Título do projeto: Geometria Computacional de Pontos em Movimento. Bolsa do cnpq até fevereiro/97. Ingresso no programa: março/96. Término: fevereiro/2000.

Em andamento

1. Fábio Ribeiro Cerqueira [J. Meidanis/IC-UNICAMP]. Título do projeto: Montagem de Fragmentos de DNA. Bolsa do cnpq até fevereiro/97. Ingresso no programa: março/96.

2. Aritanan Borges Garcia Gruber [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos e Estruturas de Dados para Problemas em Grafos Dinâmicos. Bolsa do cnpq. Ingresso no programa: março/97.

3. Said Sadique Adi [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Seqüenciamento de DNA. Bolsa do cnpq. Ingresso no programa: março/98.

4. Márcio Grossi de Almeida [Y. Kohayakawa/IME-USP]. Título do projeto: Números de Ramsey Induzidos e Semi-induzidos. Bolsa do cnpq. Ingresso no programa: março/98.

5. Cassio Polpo de Campos [C.E. Ferreira/IME-USP]. Título do projeto: Problemas Dinamicos em Geometria Computacional. Bolsa da fapesp. Ingresso no programa: março/99.

6. Eduardo Garcia de Freitas [C.E. Ferreira/IME-USP]. Título do projeto: Problemas Cineticos em Geometria Computacional. Bolsa da fapesp. Ingresso no programa: março/99.

7. Ademakson Souza Araujo [M. Lemos/DM-UFPE]. Título do projeto: Fluxos em Grafos. Bolsa do cnpq. Ingresso no programa: março/98.

8. Cláudio Tadeu Cristiano [M. Lemos/DM-UFPE]. Título do projeto: Polinômio de Tutte. Bolsa do capes. Ingresso no programa: agosto/98.

9. Débora Cristina Alves Rego [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Grafos de Interseção Geométrica. Bolsa do cnpq. Ingresso no programa: março/99.

10. Vagner Katsumi Okura [J.C. Setubal/IC-Unicamp]. Título da dissertação: Infraestrutura de bioinformática para projetos genoma. Bolsa cnpq/fapesp. Ingresso no programa: março/96.

11. Lidio Nunes de Abreu Jr. [J.C. Setubal/IC-Unicamp]. Título da dissertação: Aspectos do problema da designação. Bolsa cnpq/fapesp. Ingresso no programa: março/97.

12. Arlindo Flávio da Conceição [J.C. Setubal/IC-Unicamp]. Título da dissertação: Problemas combinatórios de congestionamento. Bolsa cnpq. Ingresso no programa: março/97.

13. Tallys Hoover Yunes [Cid de Carvalho de Souza/IC-UNICAMP]. Problemas de Escalonamento no Transporte Coletivo: Programação por Restrições e Outras Técnicas. Bolsa da fapesp. Ingresso no programa: março/98. (Em co-orientação com o Prof. Dr. Arnaldo Moura do IC-UNICAMP).

14. Marília Dias Vieira Braga [J. Meidanis/IC-UNICAMP]. Título do projeto: O Problema de Minimizar o Número de Contigs. Bolsa da fapesp. Ingresso no programa: março/98.

15. Lin Tzy Li [J. Meidanis/IC-UNICAMP]. Título do projeto: O Método OSS de Seqüenciamento de DNA. Bolsa da fapesp. Ingresso no programa: março/98.

16. Felipe Carneiro Calheiros [Cid de Carvalho de Souza/IC-UNICAMP]. Problemas de Cobertura, Empacotamento e Partição de Polígonos Retilineares. Sem bolsa (funcionário do BNDES-Rio). Ingresso no programa: março/98.

17. Eduardo Kazuaki Gondo [Cristina G. Fernandes/IME-USP]. Título do projeto: Algoritmos de Aproximação para Árvores de Steiner. Ingresso no programa: março/98.

18. Luiz Carlos Rozante [José Augusto Soares/IME-USP]. Título do Projeto: Algoritmos para Predição de Estrutura Secundária do RNA. Bolsa do cnpq. Ingresso no programa: março/98.

19. Clésio Takahashi [Cristina G. Fernandes/IME-USP]. Título do projeto: Computação Quântica. Ingresso no programa: agosto/98.

20. Maikol Magalhães Rodrigues [Cid de Carvalho de Souza/IC-UNICAMP]. Problema de Planejamento de Viagens no Transporte Coletivo Urbano. Bolsa da fapesp. Ingresso no programa: março/99.

21. Liana D. Duenha [M.H. Carvalho/DCT-UFMS]. Título do projeto: O Problema das Quatro Cores. Ingresso no programa: março/99.

22. Cândida Nunes da Silva [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Fluxos Inteiros em Grafos: Conjeturas de Tutte e Resultados Recentes. Bolsa do cnpq. Ingresso no programa: março/99.

23. Danival Taffarel Calegari [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Proposta de Extensão Criptográfica da API JavaCard. Bolsa do cnpq. Ingresso no programa: março/99.

24. Rogério Albertoni Miranda [Ricardo Dahab/IC-UNICAMP]. Título do projeto: Criptossistemas Baseados em Curvas Elípticas. Bolsa do cnpq. Ingresso no programa: março/99.

25. Ronney Rodger Sales de Castro [Cristina G. Fernandes/IME-USP]. Título do projeto: Algoritmos de Aproximação para Supercadeia Mínima e Problemas Correlatos. Bolsa do capes. Ingresso no programa: março/99.

26. Eduardo Tengan [A. Mandel/IME-USP]. Título do projeto: Uso de ideais quando poliedros falham. Ingresso no programa: agosto/99.

27. Rogério Theodoro Brito [José Augusto Soares/IME-USP]. Ingresso no programa: agosto/99.

Iniciação científica

Concluídos

1. Renato Werneck [J.C. Setubal/IC-Unicamp]. Título do projeto: Suporte computacional para projetos genoma. Bolsa da fapesp, dezembro/98 a maio/99.

2. Paulo Borges Oliva [K.S. Guimarães/DI-UFPE]. Título do projeto: Algoritmos de Aproximação. Bolsa do pibic–cnpq, agosto/97 a julho/99.

3. Cesar Augusto da Silva Scolar [J.C. Setubal/IC-Unicamp]. Título do projeto: Algoritmos e programas para determinação de estruturas em DNA genômico. Bolsa da fapesp, agosto/98 a julho/99.

4. Alerso Souza Delgado [Fábio H.V. Martinez/DCT-CCET]. Título do projeto: Mapeamento Físico de DNA. Bolsa do pibic–cnpq de agosto/98 a julho/99.

5. Graziela Santos de Araújo [Fábio H.V. Martinez/DCT-CCET]. Título do projeto: Comparação entre Múltiplas Seqüências em Biologia Molecular Computacional. Bolsa do pibic–cnpq de agosto/98 a julho/99.

6. Joe Américo Colombo [M.H. Carvalho/DCT-CCET]. Título do projeto: Emparelhamento em Grafos. Bolsa do pibic–cnpq de agosto/98 a julho/99.

7. Marcelo Abdalla dos Reis [M.H. Carvalho/DCT-CCET]. Título do projeto: O Problema das Quatro Cores. Bolsa do pibic–cnpq de agosto/98 a julho/99.

8. Welton Luiz Faria Balani [Fábio H.V. Martinez/DCT-CCET]. Título do projeto: Comparação de Duas Seqüências em Biologia Molecular Computacional. Bolsa do pibic–cnpq de agosto/98 a julho/99.

9. Alex Martins Daher [F.K. Miyazawa/IC-UNICAMP]. Título do projeto: Problemas de Empacotamento em Placas. Bolsa do pibic–cnpq de setembro/98 a julho/99.

10. Alexandre Gonçalves Silva [F.K. Miyazawa/IC-UNICAMP]. Título do projeto: O Problema de Corte Bidimensional. Bolsa do pibic–cnpq de setembro/98 a julho/99.

Em andamento

1. Guilherme Dias da Fonseca [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Título do projeto: Casamentos Estáveis. Bolsa do cnpq-UFRJ de setembro/98 a julho/2000.

2. Adriano Brito Brito Pereira [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Estudo de algoritmos gulosos. Bolsa do cnpq-UFRJ desde janeiro/99.

3. Bruno Crotman [C.M.H de Figueiredo e C.F. Bornstein/IM-COPPE-UFRJ]. Título do projeto: Algoritmos Paralelos. Bolsa do cnpq-PI de março/99 a fevereiro/2001.

4. Raphael Perret [C.M.H. de Figueiredo e C.F. Bornstein/IM-COPPE-UFRJ]. Título do projeto: Algoritmos Paralelos. Bolsa do cnpq-PI de março/99 a fevereiro/2001.

5. Thiago Souza Mendes Guimarães [C.M.H. de Figueiredo e C.F. Bornstein/IM-COPPE-UFRJ]. Título do projeto: Algoritmos Paralelos. Bolsa do cnpq-PI de março/99 a fevereiro/2001.

6. Tahuana Araujo Cirati Gomes [C.M.H. de Figueiredo e M.R. Cerioli/IM-COPPE-UFRJ]. Título do projeto: Coloração em Grafos. Bolsa do cnpq-UFRJ de setembro/99 a julho/2000.

7. Alexandre Corrêa Barbosa [J.C. Setubal/IC-Unicamp]. Título do projeto: Montagem do genoma da Xanthomonas citri. Bolsa solicitada à fapespde janeiro a junho/2000.

8. Fernando Gonçalves Urzedo [J.C. Setubal/IC-Unicamp]. Título do projeto: Suporte computacional para projetos genoma de EST. Bolsa solicitada à fapespde janeiro a junho/2000.

9. Edson Borin [M.H. Carvalho/DCT-CCET]. Título do projeto: Algoritmos para Desenho de Grafos. Bolsa do pibic–cnpq de agosto/99 a julho/2000.