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 1998 a novembro de 1999.

Formação de Recursos Humanos

1. Doutorado

1.1. Concluídos.

1. Luerbio Faria [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Bolsa da capes. Título da tese: Alguns Resultados em Invariantes de Não Planaridade em Grafos: Uma Abordagem Estrutural e de Complexidade. Término: agosto/98.

2. 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.

1.2. Em andamento.

1. Orlando Lee [Y. Wakabayashi/IME-USP]. Título da tese: Coberturas por Circuitos em Grafos Mistos. Bolsa da capes. Ingresso no programa: março/95. Data da defesa: 17/dezembro/99.

2. Bráulio Maia Junior [M. Lemos/DM-UFPE]. Título da tese: Matróides Conexas com Circunferência Pequena. Bolsa da capes. Ingresso no programa: março/97. Data da defesa: 20/dezembro/99.

3. 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.

4. 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.

5. 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.

6. 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.

Data: 30 de novembro de 1999. Projeto no. 107/97.

7. 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.

8. 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.

9. 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.

10. 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.

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

12. 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.

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

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

15. 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.

16. 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.

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

18. 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.

19. 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.

2. Mestrado

2.1. Concluídos.

1. Marco Aurélio Stefanes [J. Soares/IME-USP]. Bolsa do cnpq de março/95 a fevereiro/97. Título da dissertação: Algoritmos e Implementações Paralelas para Florestas Geradoras Mínimas. Término: fevereiro/98.

2. Edinson Raul Montoro Alegre [C.M.H. de Figueiredo/IM-COPPE-UFRJ]. Bolsa da capes. Título da dissertação: Algoritmos Dinâmicos para Árvore Geradora Mínima. Término: fevereiro/98.

3. 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.

4. Francisco Elói Soares de Araújo [J. Soares/IME-USP]. Bolsa da capes. Título da dissertação: Rearranjo de Genomas por Reversões. Término: agosto/98.

5. Cristina Célia Cavalcante [Cid de Carvalho de Souza/IC-UNICAMP]. O Problema de Escalonamento com Restrições de Mão-de-Obra. Bolsa da fapesp. Início: março/96. Término: agosto/98.

6. Lucas de Carvalho Ferreira[Ricardo Dahab/IC-UNICAMP]. Título da dissertação: Sistemas de Pagamento Eletrônico: Análise e Implementação. Bolsa do cnpq. Término: 1998.

7. Armando Ramos Gouveia [Y. Kohayakawa/IME-USP], Mestre. Bolsa da capes. Título da dissertação: Provas Holográficas de Tamanho Quase-linear. Término: novembro/98.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

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

15. 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.

2.2. Em andamento.

1. 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. Data da defesa: 13/dezembro/99.

2. 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 de 1997. Ingresso no programa: março/96.

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

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

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

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

11. 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.

12. 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.

13. 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.

14. 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.

15. 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).

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

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

22. 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.

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

24. 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.

25. 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.

26. 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.

27. 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.

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

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

3. Iniciação científica

1. Cassio Polpo de Campos [C.E. Ferreira/IME-USP]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da fapesp de fevereiro a dezembro de 1998.

2. Dan Faccio [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Rearranjo de Seqüências de DNA. Bolsa do pibic–cnpq de fevereiro de 1997 a janeiro de 1998.

3. Eduardo Garcia de Freitas [C.E. Ferreira/IME-USP]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da fapesp de fevereiro a dezembro de 1998.

4. Rodrigo Nonamor Pereira Mariano de Souza [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Árvores Filogenéticas. Bolsa do pibic–cnpq de maio a dezembro de 1998.

5. Rogério Theodoro de Brito [J. Soares/IME-USP]. Título do projeto: Compressão de Dados. Período: desde março de 1995. Bolsa do cnpq de agosto de 1995 a julho de 1997.

6. Sérgio Gabriel Tavares [C.E. Ferreira/IME-USP]. Título do projeto: Heurísticas para o Problema de Decomposição de Matrizes. Bolsa do pibic–cnpq de fevereiro de 1997 a maio de 1998.

7. Thiago Teixeira Santos [C.E. Ferreira/IME-USP]. Título do projeto: Algoritmos Combinatórios para Rearranjo de Seqüências de DNA. Bolsa do pibic– cnpq de fevereiro a dezembro de 1998.

8. Fabricio Chalub Barbosa do Rosário [S. Klein/IM-COPPE-UFRJ]. Título do projeto: Estudo e implementação de algoritmos de decomposição por conjuntos homogêneos e por pares homogêneos. Bolsa do cnpq-UFRJ de agosto de 1996 a dezembro de 1998.

9. 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 de 1998 a julho de 2000.

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

11. 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 de 1999 a fevereiro de 2001.

12. 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 de 1999 a fevereiro de 2001.

13. 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 de 1999 a fevereiro de 2001.

14. 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 de 1999 a julho de 2000.

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

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

17. 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 de 2000.

18. 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 de 2000.

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

20. 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 de 1998 a julho de 1999.

21. Paulo Fabiano Macedo [J.C. Setubal/IC-Unicamp]. Título do projeto: Implementação de algoritmo distribuído para o problema do fluxo máximo. Bolsa da fapesp, agosto de 1997 a julho de 1998.

22. Cláudia Cristina Cepukas. [J.C. Setubal/IC-Unicamp]. Título do projeto: Algoritmos perpendiculares. Bolsa da fapesp, agosto de 1997 a julho de 23. 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 de 1998 a julho de 1999.

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

25. 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 Molécular Computacional. Bolsa do pibic–cnpq de agosto de 1998 a julho de 1999.

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

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

28. 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 de 1998 a julho de 1999.