ASPECTOS ESTRUTURAIS E ALGORÍTMICOS DE OBJETOS COMBINATÓRIOS

Y. KOHAYAKAWA

Resumo. Apresentamos neste relatório as atividades científicas de nossa equipe no período de outubro de 1996 a agosto de 2000.

Sumário

1. Introdução 2 2. Equipe 3 3. Publicações 4 4. Orientações 9 5. Viagens 12 6. Visitantes 17 7. Eventos 18 8. Auxílios Vigentes 21 9. Prêmios e Honrarias 23 10. Outras Atividades 24 11. Conclusão e Análise Crítica 24

Data: 24 de agosto de 2000. Processo fapesp 96/04505–2.

1. Introdução

Este relatório científico refere-se ao período de outubro de 1996 a agosto de 2000. Enumeramos sucintamente aqui algumas informações para dar uma idéia inicial de nossas atividades neste período.

1.1. Equipe. A equipe do projeto temático Aspectos Estruturais e Algorítmicos de Objetos Combinatórios (Proc. fapesp no. 96/04505–2) é formada atualmente por 8 professores doutores do Departamento de Ciência da Computação da Universidade de São Paulo.

O grupo recebeu a visita de cerca de 25 pesquisadores estrangeiros durante o período, cujas permanências variaram desde alguns dias a algumas semanas. A equipe também contou com um visitante de longa duração, o prof. Bruce Reed (financiado pela fapesp), que deu grande impulso às atividades do grupo.

Esta equipe é atualmente responsável por 10 alunos de doutorado e 12 alunos de mestrado, e orienta ou orientou 10 alunos de iniciação científica no período referente a este relatório. Durante este período, a equipe formou 2 doutores e 12 mestres.

1.2. Publicações. A lista de publicações no período consiste de 29 artigos (publicados e aceitos para publicação) e 14 submissões em periódicos internacionais com arbitragem, 2 artigos em periódico nacional, 21 trabalhos completos/resumos estendidos em anais de congressos nacionais e internacionais e coletâneas e 2 livros. Ademais, encontram-se em preparação 13 outros artigos, totalizando com as submissões 27 trabalhos a serem publicados nos próximos anos.

Vários membros da equipe participaram de eventos internacionais e nacionais, tendo apresentado cerca de 20 trabalhos.

Embora o volume de trabalhos publicados por nossa equipe não seja grande, destacamos que estes trabalhos apareceram em periódicos de primeira linha, como Journal of Algorithms, Journal of Combinatorial Theory, Series B, Combinatorica, SIAM Journal on Optimization, SIAM Journal on Computing, Algorithmica, Acta Arithmetica, Journal of the London Mathematical Society, Journal of Algebra, e Annals of Applied Probability, e também em congressos de alta competitividade, como o ACM–SIAM Symposium on Discrete Algorithms (SODA), Integer Programming and Combinatorial Optimization (IPCO) e IEEE Annual Symposium on Foundations of Computer Science (FOCS).

1.3. Eventos e seminários. A nossa equipe realizou os seguintes eventos no período: Workshop on Probabilistic Methods in Combinatorics and Theoretical Computer Science, o Dia da Combinatória, uma série de Lectures on Tree-decom-positions, Permanents, Pfaffian Orientations and Even Directed Circuit, um Minicurso sobre Bases de Gröbner, e o Dia de Otimização e Combinatória.

Na oficina de métodos probabilísticos mencionada acima, participaram pesquisadores como N. Alon, Z. Füredi, P. Pudlák, e J.H. Kim. Tivemos portanto 3 palestrantes de Congressos Internacionais de Matemáticos [Tóquio (NA), Zurique (ZF e PP)] e um ganhador da Medalha Fulkerson [Lausanne (JHK)]! A série de palestras sobre decomposição arbórea e temas correlatos ficou sob a responsabilidade do prof. R. Thomas, um dos expoentes máximos na teoria de Robertson-Seymour.

Naturalmente, a equipe mantém e participa ativamente de um seminário semanal com a participação de visitantes estrangeiros do grupo e pesquisadores nacionais de outras instituições ou departamentos.

1.4. Aquisição de equipamento. Foram adquiridos através da verba deste projeto temático 10 X-terminais HP Envizex, com o objetivo de equipar os membros do grupo que ainda não dispunham de terminais, e reequipar aqueles que dispunham de equipamentos já obsoletos.

Igualmente importante foram os pedidos complementares que foram feitos ao longo do projeto.

2. Equipe

2.1. Pesquisadores. A equipe consiste dos seguintes membros do Departamento de Ciência da Computação da USP:

1. Arnaldo Mandel, PhD, Waterloo, 1982; especialidades: matróides, teoria de anéis.

2. Carlos Eduardo Ferreira, Dr. rer. nat., Tech. Uni., Berlim, 1994; métodos poliédricos e otimização combinatória em geral.

3. Cristina Gomes Fernandes, PhD, Georgia Tech, 1997; algoritmos on-line e algoritmos de aproximação. [Esteve afastada para cumprir programa de doutoramento; retornou em julho de 1997]

4. José Augusto Ramos Soares, PhD, Chicago, 1992; algoritmos combinatórios, problemas extremais, compressão de dados.

5. José Coelho de Pina Júnior, Doctor, Amsterdã, 1995; algoritmos combinatórios.

6. Maria Angela de Campos Gurgel, Doutora, USP, 1992; métodos poliédricos em otimização combinatória. [Aposentada 1998]

7. Paulo Feofiloff, PhD, Waterloo, 1983; otimização combinatória, identidades minmax.

8. Yoshiharu Kohayakawa, PhD, Cambridge, 1990; métodos probabilísticos, problemas extremais. [Coordenador do projeto]

9. Yoshiko Wakabayashi, Dr. rer. nat., Augusburg, 1986; grafos, métodos poliédricos e otimização combinatória em geral.

2.2. Alunos envolvidos. A equipe é atualmente responsável pelos seguintes alunos do nosso departamento.

– Doutorado: 1. Estela Maris Rodrigues, Mestre, USP

2. Fábio H. Viduane Martinez, Mestre, USP 3. Francisco Elói Soares de Araujo, Mestre, USP 4. Glauber Ferreira Cintra, Mestre, USP

5. Jair Donadelli Júnior, Mestre, USP

6. Liliane Rose Benning Salgado, Mestre, UFPE 7. Marco Aurélio Stefanes, Mestre, USP

8. Mário Leston Rey, Mestre, USP

9. Ranato J. da S. Carmo, Mestre, USP

10. Said Sadique Adi, Mestre, USP.

– Mestrado: 1. Alexandre Noma

2. Aritanan Borges Garcia Gruber

3. Cássio Polpo de Campos

4. Eduardo Garcia de Freitas

5. Eduardo Kazuaki Gondo 6. Eduardo Tengan

7. Gordana Maric

8. José Osvaldo Couto Horta

9. Luiz Carlos Rozante

10. Rogério Theodoro Brito

11. Ronney Rodger Sales de Castro

12. Shigueo Isotani

– Iniciação científica (no período): Alexandre Cardoso Garcia Leite, Bruno Leite, Cassio Polpo de Campos, Dan Faccio, Eduardo Garcia de Freitas, Luciano Micheletti Hespanhol, Rodrigo Nonamor Pereira Mariano de Souza, Rogério Brito, Sérgio Gabriel Tavares, Thiago Teixeira Santos.

2.3. Alunos formados. Durante o período, a equipe formou os seguintes alunos.

– Doutorado:

1. Flávio Keidi Miyazawa (Mestre-USP), doutorou-se em dezembro/1997.

2. Orlando Lee (Mestre-USP), doutorou-se em dezembro/1999.

– Mestrado:

1. César Alberto Bravo Pariente, obteve o grau de mestre em novembro/1996.

2. Armando Ramos Gouveia, obteve o grau de mestre em novembro/1998.

3. Estela Maris Rodrigues, obteve o grau de mestre em fevereiro/1997.

4. Francisco Elói Soares de Araujo, obteve o grau de mestre em agosto/1998.

5. Glauber Ferreira Cintra, obteve o grau de mestre em julho/1998.

6. Marco Aurélio Stefanes, obteve o grau de mestre em fevereiro/1998.

7. Alexandre Scalzitti, obteve o grau de mestre em outubro/1999.

8. Mário Leston Rey, obteve o grau de mestre em novembro/1999.

9. Edésio R. Sibrão, obteve o grau de mestre em dezembro/1999.

10. Carlos R. Pantaleon Dionisio, obteve o grau de mestre em fevereiro/2000.

11. Said Sadique Adi, obteve o grau de mestre em abril/2000.

12. Márcio Grossi de Almeida, obteve o grau de mestre em junho/2000.

2.4. Página na Teia. Mantemos uma página com informações sobre o projeto e atividades afins.

http://www.ime.usp.br/~cris/gcomb/tem-fapesp/

Usamos a página acima para manter amplamente disponíveis versões eletrônicas da grande maioria dos nossos trabalhos científicos, como proposto em nosso projeto inicial.

3. Publicações

Observação. Enumeramos abaixo as publicações de nosso grupo no período coberto por este relatório. Observamos que algumas publicações são fruto de trabalhos anteriores (por outro lado, algumas publicações, fruto de trabalho no período, não aparecem abaixo). Incluímos também vários trabalhos do prof. Bruce Reed elaborados durante a sua estadia conosco (veja Seção 6). Esperamos que a inclusão destes trabalhos forneça uma fotografia mais completa, como um todo, da produção científica de nosso grupo no período contemplado neste relatório.

3.1. Periódicos internacionais arbitrados.

1. B. Bollobás, Y. Kohayakawa, and R.H. Schelp, Essentially infinite colourings of graphs, The Journal of the London Mathematical Society. Second Series 61 (2000), no. 3, 658–670.

2. R. Borndörfer, C.E. Ferreira, and A. Martin, Decomposing matrices into blocks, SIAM Journal on Optimization 9 (1999), no. 1, 236–269.

3. G. Călinescu, C.G. Fernandes, U. Finkler, and H. Karloff, A better approximation algorithm for finding planar subgraphs, Journal of Algorithms 27 (1998), 269–302.

4. C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa, and B. Reed, Finding skew partitions efficiently, Journal of Algorithms, to appear.

5. P. Erdős, A. Gyárfás, and Y. Kohayakawa, The size of the largest bipartite subgraphs, Discrete Mathematics 177 (1997), no. 1–3, 267–271.

6. C.G. Fernandes, A better approximation ratio for the minimum k-edge-connected spanning subgraph problem, Journal of Algorithms 28 (1998), 105– 124.

7. C.E. Ferreira, C.C. de Souza, and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Discrete Applied Mathematics, to appear.

8. L.R.G. Fontes, M. Isopi, Y. Kohayakawa, and P. Picco, The spectral gap of the REM under the Metropolis dynamics, Annals of Applied Probability 8 (1998), no. 3, 917–943.

9. J.Z. Gonçalves and A. Mandel, Free subgroups in the group of units of a twisted group algebra, Communications in Algebra, to appear.

10. J.Z. Gonçalves, A. Mandel, and M. Shirvani, Free products of units in algebras. II. Crossed products, Journal of Algebra, to appear.

11. , Free products of units in algebras. I. Quaternion algebras, Journal of Algebra 214 (1999), no. 1, 301–316.

12. M.A.M.C. Gurgel and Y. Wakabayashi, Adjacency of vertices of the complete pre-order polytope, Discrete Mathematics 175 (1997), no. 1–3, 163–172.

13. R.F. Hashimoto, J. Barrera, and C.E. Ferreira, A combinatorial optimization technique for the sequential decomposition of erosions and dilations, Journal of Mathematical Imaging and Vision 13 (2000), no. 1, 17–33.

14. P.E. Haxell and Y. Kohayakawa, Partitioning by monochromatic trees, Journal of Combinatorial Theory , Series B 68 (1996), no. 2, 218–222.

15. , Packing and covering triangles in tripartite graphs, Graphs and Combinatorics 14 (1998), no. 1, 1–10.

16. P.E. Haxell, Y. Kohayakawa, and T. Łuczak, Turán’s extremal problem in random graphs: forbidding odd cycles, Combinatorica 16 (1996), no. 1, 107–122.

17. Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures and Algorithms 11 (1997), no. 3, 245–276.

18. Y. Kohayakawa, B. Kreuter, and D. Osthus, The length of random subsets of Boolean lattices, Random Structures Algorithms 16 (2000), no. 2, 177–194.

19. Y. Kohayakawa, B. Kreuter, and A. Steger, An extremal problem for random graphs and the number of graphs with large even-girth, Combinatorica 18 (1998), no. 1, 101–120.

20. Y. Kohayakawa, T. Łuczak, and V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arithmetica LXXV (1996), no. 2, 133–163.

21. Y. Kohayakawa, T. Łuczak, and V. Rödl, Ramsey-type results for oriented trees, Journal of Graph Theory 22 (1996), no. 1, 1–8.

22. Y. Kohayakawa, T. Łuczak, and V. Rödl, On K^{4}-free subgraphs of random graphs, Combinatorica 17 (1997), no. 2, 173–213.

23. Y. Kohayakawa, H.-J. Prömel, and V. Rödl, Induced Ramsey numbers, Combinatorica 18 (1998), no. 3, 373–404.

24. F.K. Miyazawa and Y. Wakabayashi, An algorithm for the three-dimensional packing problem with asymptotic performance analysis, Algorithmica 18 (1997), no. 1, 122–144.

25. , Approximation algorithms for the orthogonal z-oriented 3-D packing problem, SIAM Journal on Computing 29 (2000), no. 3, 1008–1029.

26. B. Reed, The list colouring constants, Journal of Graph Theory 31 (1999), no. 2, 149–153.

27. , Mangoes and blueberrie, Combinatorica 19 (1999), no. 2, 267–296.

28. , A strengthening of Brooks’ theorem, Journal of Combinatorial Theory, Series B 76 (1999), no. 2, 136–149.

29. B. Reed and R. Thomas, Clique minors in graphs and their complement, Journal Combinatorial Theory , Series B 78 (2000), no. 1, 81–85.

3.2. Periódicos nacionais.

1. C.E. Ferreira, F.K. Miyazawa, and Y. Wakabayashi, Packing of squares into squares, Pesquisa Operacional 19 (2000), no. 2, in press.

2. Y. Wakabayashi, The complexity of computing medians of relations, Resenhas 3 (1998), no. 3, 323–349, [indexado no Mathematical Reviews].

3.3. Livros.

1. P. Feofiloff, Algoritmos de programação linear, Editora da Universidade de São Paulo, 1999.

2. C.E. Ferreira and Y. Wakabayashi, Planos-de-corte faciais e a resolução de problemas de otimização combinatória, I Encontro de Matemática Aplicada e Computacional, ERMAC, São Paulo, Brasil, Junho 1998.

3.4. Anais de Congressos Internacionais e Coletâneas.

1. N. Alon, M.R. Capalbo, Y. Kohayakawa, V. Rödl, A. Ruciński, and E. Szemerédi, Universality and tolerance (extended abstract), Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2000), 2000, a aparecer.

2. J. Barrera, C.E. Ferreira, and R.F. Hashimoto, Finding optimal sequential decompositions of erosions and dilations, Mathematical morphology and its applications to image and signal processing (Kluwer Academic, ed.), 1998.

3. B. Bollobás and Y. Kohayakawa, On Richardson’s model on the hypercube, Combinatorics, Geometry and Probability (B. Bollobás and A. Thomason, eds.), Cambridge University Press, Cambridge, 1997, ISBN 0 521 584728, pp. 129– 137.

4. G. Călinescu, C.G. Fernandes, and B. Reed, Multicuts in unweighted graphs with bounded degree and bounded tree-width, Integer Programming and Combinatorial Optimization (Berlin) (R. E. Bixby, E. A. Boyd, and R. Z. Ríos-Mercado, eds.), Lecture Notes in Computer Science, vol. 1412, Springer, 1998, pp. 137–152.

5. G.F. Cintra and Y. Wakabayshi, A hybrid algorithm for the one-dimensional cutting stock problem, Proceedings of the XVII International Symposium on Math. Programming, 2000, abstract.

6. C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa, and B. Reed, Finding skew partitions efficiently, Proceedings of LATIN’2000: theoretical informatics (Berlin), Lecture Notes in Comput. Sci., Springer, April 2000, pp. 163–172.

7. J.C. de Pina and J. Soares, Improved bound for the Carathéodory rank of the bases of a matroid, Proceedings of the XVII International Symposium on Math. Programming, 2000, abstract.

8. , A new bound for the Carathéodory rank of the bases of a matroid, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 642–643.

9. C.G. Fernandes, A better approximation ratio for the minimum k-edge-connected spanning subgraph problem, Proc. 8th Annual ACM–SIAM Symposium on Discrete Algorithms (EUA), 1997, pp. 629–638.

10. C.G. Fernandes, O. Lee, and Y. Wakabayashi, The chinese postman and the minimum circuit problem on mixed graphs, Proceedings of the XVII International Symposium on Math. Programming, 2000, abstract.

11. C.E. Ferreira, C.C. de Souza, and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Proceedings of the 2nd Workshop on Practical Combinatorial Optimization Problems (Valparaiso, Chile), novembro 1996.

12. , A polyhedral approach for DNA fragments rearrangement, Proc. of the XVI International Symposium on Math. Programming (Lausanne), agosto 1997, abstract.

13. Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of Computational Mathematics (Berlin, Heidelberg) (F. Cucker and M. Shub, eds.), Springer-Verlag, January 1997, pp. 216–230.

14. Y. Kohayakawa and V. Rödl, Algorithmic aspects of regularity (invited paper), LATIN’2000: Theoretical Informatics (Punta del Este, 2000) (G. Gonnet, D. Panario, and A. Viola, eds.), Lecture Notes in Computer Science, Springer, Berlin, 2000, pp. 1–17.

15. Y. Kohayakawa, V. Rödl, and J. Skokan, Equivalent conditions for regularity (extended abstract), LATIN’2000: Theoretical Informatics (Punta del Este, 2000) (G. Gonnet, D. Panario, and A. Viola, eds.), Lecture Notes in Computer Science, Springer, Berlin, 2000, pp. 48–57.

16. O. Lee and Y. Wakabayashi, Circuit covers in series-parallel mixed graphs, Proceedings of the XVI International Symposium on Math. Programming, 1997, abstract.

17. , Circuit covers in series-parallel mixed graphs, LATIN’98: Theoretical Informatics (Campinas, Brazil) (C.L. Lucchesi and A.V. Moura, eds.), Lecture Notes in Computer Science, vol. 1380, Springer-Verlag, abril 1998, pp. 226–238.

18. F.K. Miyazawa and Y. Wakabayashi, Approximation algorithms for packing problems with orthogonal rotations, Proceedings of the XVI International Symposium on Math. Programming, 1997, abstract.

19. , Cube packing, Proceedings of LATIN’2000: theoretical informatics (Berlin), Lecture Notes in Comput. Sci., Springer, April 2000, (Punta del Este, Uruguay), pp. 58–67.

20. M. Molloy and B. Reed, A pseudo-random method for list colourings, Proceedings of WAIT (Buenos Aires, Argentina), 1997.

21. , Colouring graphs whose chromatic number is almost their maximum degree, Proceedings of LATIN’98: Theoretical Informatics (Campinas, Brazil) (C.L. Lucchesi and A.V. Moura, eds.), Lecture Notes in Computer Science, vol. 1380, Springer-Verlag, 1998, pp. 216–225.

3.5. Anais de Congressos Nacionais.

1. G.F. Cintra and Y. Wakabayashi, Um algoritmo híbrido para o problema de corte unidimensional, XXX SOBRAPO, Anais da III Oficina de Problemas de Corte e Empacotamento (Curitiba), 1998, pp. 79–96.

2. C.E. Ferreira e E.R. Sibrão, Escalonamento em sistemas de produção: um estudo de caso, Proceedings do XXX Simpósio Brasileiro de Pesquisa Operacional, 1998, (Curitiba, Paraná), pp. 123–130.

3. C.E. Ferreira and M. Loparić, Uma aplicação do método branch-and-cut a um problema de roteamento de veículos, Anais do Concurso de Dissertações e Teses da SBC, 1997, pp. 509–516.

4. F.K. Miyazawa and Y. Wakabayashi, Three-dimensional packing problem: Approximation algorithms and performance analysis, Anais da I Oficina Nacional em Problemas de Corte e Empacotamento, 1996, Tech. Report RT-MAC-9610, IME-USP, pp. 11–16.

5. , Approximation algorithms for packing small items, XX CNMAC - Anais da II Oficina Nacional de Problemas de Cortes e Empacotamento, 1997, pp. 7–14.

6. , Parametric on-line packing, XXX SOBRAPO, Anais da III Oficina de Problemas de Corte e Empacotamento (Curitiba), 1998, pp. 109–121.

3.6. Trabalhos submetidos.

1. G. Călinescu, C.G. Fernandes, H. Karloff, and A. Zelikovski, A new approximation algorithm for finding heavy planar subgraphs, submetido, 1998.

2. J.C. de Pina and J. Soares, Improved bound for the Carathéodory rank of the bases of a matroid, submetido, 1999.

3. J. Donadelli and Y. Kohayakawa, A density result for random sparse oriented graphs and its relation to a conjecture of Woodall, submetido, 2000.

4. M.A.M.C. Gurgel and Y. Wakabayashi, The complete pre-order polytope: facets and separation problem, submetido, 1998.

5. Y. Kohayakawa and B. Kreuter, The width of random subsets of Boolean lattices, submetido, 1998.

6. O. Lee and Y. Wakabayashi, On a conjecture of Woodall for series-parallel digraphs, submetido, 1999.

7. M. Loparic and C.E. Ferreira, A branch-and-cut algorithm for a vehicle routing problem with capacity and time constraints, submetido, 1997.

8. F.K. Miyazawa and Y. Wakabayashi, Cube packing, submetido, 2000.

9. , Parametric on-line approximation algorithms for packing rectangles and boxes, submetido, 2000.

10. M. Molloy and B. Reed, Colouring graphs whose chromatic number is almost their maximum degree, submetido, 1998.

11. , Further algorithmic aspects of the local lemma, submetido, 1998.

12. , A pseudo-random method for list colourings, submetido, 1998.

13. M. Molloy, B. Reed, and W. Steiger, On the mixing rate of the triangulation walk, submetido, 1998.

14. H. van der Holst and J.C. de Pina, Length-bounded disjoint paths in planar graphs, submetido, 1999.

3.7. Em preparação.

1. N. Alon, M.R. Capalbo, Y. Kohayakawa, V. Rödl, A. Ruciński, and E. Szemerédi, Universality and tolerance, em preparação, 2000.

2. B. Bollobás, Y. Kohayakawa, and A. Taraz, Essentially infinite colourings of hypergraphs, em preparação, 2000.

3. G.F. Cintra and Y. Wakabayashi, A hybrid quasi-exact algorithm for the onedimensional cutting stock problem, em preparação, 2000.

4. J.C. de Pina, A note on integral pontentials, em preparação, 2000.

5. , Shortest circuit base of graphs, em preparação, 2000.

6. Y. Kohayakawa, B. Nagle, and V. Rödl, Hereditary properties of triple systems, em preparação, 2000.

7. Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs I, em preparação, 2000.

8. , Regular pairs in sparse random graphs II, em preparação, 2000.

9. Y. Kohayakawa, V. Rödl, and J. Skokan, Equivalent conditions for regularity, em preparação, 2000.

10. Y. Kohayakawa, V. Rödl, and E. Szemerédi, The size-Ramsey number of graphs of bounded degree, em preparação, 2000.

11. Y. Kohayakawa, V. Rödl, and L. Thoma, An optimal deterministic algorithm for checking regularity, em preparação, 2000.

12. O. Lee and Y. Wakabayashi, Circuit covers and minimum circuits in mixed graphs, em preparação, 2000.

13. M.-F. Sagot and Y. Wakabayashi, Pattern inference under many guises, em preparação, 2000.

4. Orientações

Enumeramos os alunos sob nossa responsabilidade no período, especificando o orientador em cada caso.

4.1. Doutorado.

1. Estela Maris Rodrigues [Y. Wakabayashi]. Título do projeto: Algoritmos de Inferência Filogenética, Partições e outras Estruturas Discretas (título provisório). Bolsa do cnpq. Ingresso no programa: março de 1997. Em andamento.

2. Fábio H. Viduani Martinez [J. Soares]. Título do projeto: Algoritmos Paralelos (título provisório). Ingresso no programa: agosto de 1999. Em andamento.

3. Flávio Keidi Miyazawa [Y. Wakabayashi]. Doutor. Formou-se em novembro de 97. Bolsa do cnpq. Título da tese: Algoritmos de Aproximação para Problemas de Empacotamento. Atualmente membro do Instituto de Computação da UNICAMP.

4. Francisco Elói Soares de Araújo [J. Soares]. Título do projeto: Biologia Computacional. Ingresso no programa: agosto de 1998. Em andamento.

5. Glauber Ferreira Cintra [Y. Wakabayashi]. Título do projeto: Problemas de Empacotamento e Roteamento de Cargas (título provisório). Bolsa do cnpq desde outubro de 1999. Ingresso no programa: agosto de 1998. Em andamento.

6. Jair Donadelli Júnior [Y. Kohayakawa]. Título do projeto: Métodos Probabilísticos e Métodos Topológicos em Combinatória Extremal. Bolsa da capes até dezembro de 97 e bolsa do cnpq desde janeiro de 1998. Ingresso no programa: março de 1996. Em andamento.

7. Liliane Rose Benning Salgado [Y. Wakabayashi]. Título do projeto: Aproximabilidade de Problemas de Otimização em Grafos. Bolsa da fapesp desde agosto de 1998. Ingresso no programa: março de 1998. Em andamento.

8. Marco Aurélio Stefanes [J. Soares]. Título do projeto: Algoritmos Paralelos para Grafos e Geometria Computacional. Bolsa da fapesp desde agosto de 1998. Ingresso no programa: março de 1998. Em andamento.

9. Mário Leston Rey [Y. Wakabayashi]. Título do projeto: Aspectos Estrturais e Algorítmicos de Problemas em Teoria dos Grafos (título provisório). Ingresso no programa: março de 2000. Em andamento.

10. Orlando Lee [Y. Wakabayashi]. Doutor. Formou-se em dezembro de 1999. Bolsa do capes. Título da tese: Cobertura por Circuitos em Grafos Mistos. Pleiteando bolsa para fazer pós-doutorado no exterior.

11. Renato J. da S. Carmo [Y. Kohayakawa] Título do projeto: Análise de Caso Médio de Algoritmos e Grafos Aleatórios (título provisório). Ingresso no programa: março de 2000. Em andamento.

12. Said Sadique Adi [C.E. Ferreira]. Título de projeto: Ferramentas para dissecação de genomas (título provisório). Ingresso no programa: agosto de 2000. Em andamento.

4.2. Mestrado.

1. Alexandre Noma [C.G. Fernandes] Título do projeto: Análise experimental de algoritmos para teste planaridade (título provisório). Ingresso no programa: março de 2000. Bolsa da fapesp. Em andamento.

2. Alexandre Scalzitti [Y. Kohayakawa], Mestre. Formou-se em outubro de 1999. Título da dissertação: Convergência na Teoria dos Grafos Aleatórios.

3. Aritanan Borges Garcia Gruber [C.E. Ferreira]. Título do projeto: Algoritmos Dinâmicos para Problemas de Otimização Combinatória. Bolsa do cnpq. Ingresso no programa: março de 1997. Em andamento.

4. Armando Ramos Gouveia [Y. Kohayakawa], Mestre. Formou-se em novembro de 1998. Bolsa da capes. Título da dissertação: Provas Holográficas de Tamanho Quase-linear.

5. Carlos R. Pantaleon Dionisio [J.C. de Pina], Mestre. Formou-se em fevereiro de 2000. Bolsa do cnpq até fevereiro de 1997. Título da dissertação: Geometria Computacional de Pontos em Movimento.

6. Cássio Polpo de Campos [C.E. Ferreira]. Título do projeto: Algoritmos Dinâmicos em Geometria Computacional (título provisório). Ingresso no programa: março de 1999. Bolsa da fapesp. Em andamento.

7. César Alberto Bravo Pariente [Y. Kohayakawa], Mestre. Formou-se em novembro de 96. Bolsa da capes. Título da dissertação: Um Método Probabilístico em Combinatória.

8. Edésio R. Sibrão [C.E. Ferreira], Mestre. Formou-se em dezembro de 1999. Bolsa da capes de agosto de 1996 até julho de 1998. Título da dissertação: Escalonamento em Sistemas de Produção: um Estudo de Caso.

9. Eduardo Garcia de Freitas [C.E. Ferreira]. Título do projeto: Algoritmos Cinéticos em Geometria Computacional (título provisório). Ingresso no programa: março de 1999. Bolsa da fapesp. Em andamento.

10. Eduardo Kazuaki Gondo [C.G. Fernades]. Título do projeto: Algoritmos de Aproximação para o Problema da Árvore de Steiner Mínima (título provisório). Ingresso no programa: março de 1999. Em andamento.

11. Eduardo Tengan [A. Mandel]. Título do projeto: Bases de Gröbner e suas amplicações em topologia algébrica de corpos finitos não-comutativos com unidade (título provisório). Ingresso no programa: março de 2000. Em andamento.

12. Estela Maris Rodrigues [M.A.M.C Gurgel], Mestre. Formou-se em fevereiro de 1997. Bolsa do cnpq. Título da dissertação: Fatores e Empacotamentos em Grafos.

13. Francisco Elói Soares de Araújo [J. Soares], Mestre. Formou-se em agosto de 1998. Bolsa da capes. Título da dissertação: Rearranjo de Genomas por Reversões.

14. Glauber Ferreira Cintra [Y. Wakabayashi], Mestre. Formou-se em julho de 1998. Bolsa do cnpq. Título da dissertação: Algoritmos Híbridos para Problemas de Corte Unidimensional.

15. Gordana Manic [P. Feofiloff]. Título do projeto: Análise experimental de algoritmos para junções e orelhas (título provisório). Ingresso no programa: agosto de 1999. Bolsa do capes. Em andamento.

16. Luiz Carlos Rozante [J. Soares]. Título do projeto: Algoritmos para Predição da Estrutura Secundária do RNA (título provisório). Ingresso no programa: março de 1999. Bolsa do cnpq. Em andamento.

17. Marco Aurélio Stefanes [J. Soares], Mestre. Formou-se em fevereiro de 1998. Bolsa do cnpq de março de 95 a fevereiro de 97. Título da dissertação: Algoritmos e Implementações Paralelas para Florestas Geradoras Mínimas.

18. Márcio Grossi de Almeida [Y. Kohayakawa], Mestre. Formou-se em junho de 1999. Bolsa da capes em 1998 e bolsa do cnpq de maio de 1999 a abril de 2000. Título da dissertação: Números de Ramsey Induzidos e Semi-induzidos.

19. Mário Leston Rey [P. Feofiloff], Mestre. Formou-se em novembro de 1999. Bolsa do cnpq. Título da dissertação: T -junções, T -cortes e Funções Conservativas.

20. Rogério Theodoro Brito [J. Soares]. Título do projeto: Teoria dos Números Algorítmica (título provisório). Ingresso no programa: março de 2000. Em andamento.

21. Ronney Rodeger Sales de Castro [C.G. Fernades]. Título do projeto: Algoritmos de Aproximação para Subgrafos k-Aresta Conexo Mínimo (título provisório). Ingresso no programa: março de 1999. Bolsa do capes. Em andamento.

22. Said Sadique Adi [C.E. Ferreira], Mestre. Formou-se em abril de 2000. Bolsa do capes. Título da dissertação: Ferramentas de Auxilio ao Sequenciamento de DNA por montagem de fragmentos: um estudo comparativo.

23. Shigueo Isotani [J.C. de Pina]. Título do projeto: Caminho mínimo em tempo linear (título provisório). Ingresso no programa: março de 2000. Bolsa do capes. Em andamento.

4.3. Iniciação científica.

1. Alexandre Cardoso Garcia Leite [J. Soares]. Título do projeto: Problemas Combinatórios de Busca. Período: de março de 1995 a fevereiro de 1997. Bolsa do cnpq de agosto de 1995 a fevereiro de 1997.

2. Bruno Leite [Y. Kohayakawa, em conjunto com Edson de Faria, ime-usp]. Título do projeto: Matemática Concreta e Teoria Analítica dos Números. Período: desde março de 2000. Bolsa da fapesp será pleiteada. Este aluno foi o 2o. colocado (classificação geral) na FUVEST de 2000.

3. Cassio Polpo de Campos [C.E. Ferreira]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da fapesp (Processo: 97/09521-9) de fevereiro a dezembro de 1998.

4. Dan Faccio [C.E. Ferreira]. 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.

5. Eduardo Garcia de Freitas [C.E. Ferreira]. Título do projeto: Geometria Computacional: Algoritmos e Aplicações. Bolsa da fapesp (Processo: 97/09522-5) de fevereiro a dezembro de 1998.

6. Luciano Micheletti Hespanhol [J. Soares]. Título do projeto: Compressão de Dados. Bolsa do PIBIC–cnpq de outubro de 1996 a fevereiro de 1997.

7. Rodrigo Nonamor Pereira Mariano de Souza [C.E. Ferreira]. Título do projeto: Algoritmos Combinatórios para Árvores Filogenéticas. Bolsa do PIBIC–cnpq desde maio de 1998 a junho de 1999.

8. Rogério Theodoro de Brito [J. Soares]. 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.

9. Sérgio Gabriel Tavares [C.E. Ferreira]. 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.

10. Thiago Teixeira Santos [C.E. Ferreira]. Título do projeto: Algoritmos Combinatórios para Rearranjo de Seqüências de DNA. Bolsa do PIBIC–cnpq desde fevereiro de 1998 a julho de 1999.

5. Viagens

5.1. Eventos internacionais.

1. DIMACS Workshop on Probabilistic Methods in Discrete Mathematics, DI-MACS (EUA), 14–18 de outubro de 1996. Y. Kohayakawa participou, com despesas pagas pelo encontro.

2. InFORMS’96 – Institute for Operations Research and the Management Sciences Meeting, Atlanta-GA (EUA), 3–6 de novembro/96.

– C.G. Fernandes apresentou o trabalho A Better Approximation Algo-

rithm for Finding Planar Subgraphs.

3. II ALIO/EURO Workshop on Practical Combinatorial Optimization, Val-

paraiso (Chile), 11–15 de novembro/96.

– C.E. Ferreira apresentou o trabalho Rearrangement of DNA fragments:

a branch-and-cut algorithm.

4. SODA’97 – 8^{th} Annual ACM-SIAM Symposium on Discrete Algorithms,

New Orleans-LA (EUA), 5–7 de janeiro/97.

– C.G. Fernandes apresentou o trabalho A Better Approximation Ratio

for the Minimum k-Edge-Connected Spanning Subgraph Problem.

5. FoCM’97 – Foundations of Computational Mathematics, IMPA, Rio de Ja-

neiro, 5–12 de janeiro/97.

– Y. Kohayakawa (Proc. 97/01873–3 - fapesp) participou da oficina Relations to Computer Science. Apresentou o trabalho Szemerédi’s Regularity Lemma for Sparse Graphs (semi-plenária, 50 minutos).

– Y. Wakabayashi (Proc. 96/12820–5 - fapesp) participou do Workshop on Optimization. Apresentou o trabalho Approximation Algorithms for Three-dimensional Packing Problems.

6. STOC’97 – 29^{th} Annual ACM Symposium on Theory of Computing (STOC),

El Paso-TX (EUA), 4–6 de maio/97.

– Participante: C.G. Fernandes.

7. WAIT ’97, First Argentine Workshop on Theoretical Informatics, Buenos

Aires, 11 de agosto de 1997.

– Y. Kohayakawa proferiu uma palestra convidada, intitulada Pseudoran-

domness in Graph Theory. Participação financiada pelos organizadores.

8. ISMP’97 – XVI International Symposium on Mathematical Programming,

Lausanne, Suíça, 24–29 de agosto/97.

– C.E. Ferreira apresentou o trabalho A Polyhedral Approach for DNA Fragments Arrangement. Financiado pelo ProBRAL 001/94.

– F.K. Miyazawa apresentou o trabalho Approximation Algorithms for Packing Problems with Orthogonal Rotations. Financiado pelo Pro-BRAL 001/94.

– Y. Wakabayashi (Proc. 97/6472-7 - fapesp) apresentou o trabalho Cir-

cuit Covers in Mixed Graphs.

9. Random Graphs and Combinatorial Structures, Oberwolfach, Alemanha,

28 de setembro a 4 de outubro de 1997.

– Y. Kohayakawa apresentou o trabalho Checking Pseudorandomness of

Graphs Fast. Despesas locais cobertas pelos organizadores.

10. LATIN ’98 – Third Latin American Symposium on Theoretical INformatics, UNICAMP, 20–24 de abril/98. Simpósio internacional dedicado à teoria da computação. Participaram vários membros do grupo. Y. Kohayakawa fez parte do Comitê de Programa.

– O. Lee apresentou o trabalho Circuit Covers in Series-parallel Mixed

Graphs.

11. From Erdős to Algorithms, DIMACS, 8–10 de junho de 1998. Evento orga-

nizado conjuntamente pelo DIMACS e DIMATIA (Praga).

– Y. Kohayakawa apresentou o trabalho Random Sperner-type Results. Participação financiada pelos organizadores.

12. IPCO’98 – 6^{th} Conference on Integer Programming and Combinatorial Op-

timization, Houston-TX (EUA), 22–24 de junho/98.

– C.G. Fernandes apresentou o trabalho Multicuts in Unweighted Graphs

with Bounded Degree and Bounded Tree-Width. Financiada pelo cnpq.

13. Probabilistic Combinatorics, Mathematical Institute, Budapest, 25 de junho a 8 de julho de 1998. Y. Kohayakawa participou, com despesas locais pagas pelo encontro e passagem paga pelo projeto Complexidade de Estruturas Discretas (pronex).

14. 5th Czech-Slovak International Symposium on Combinatorics, Graph The-

ory, Algorithms and Applications, Praga, 6 a 11 de julho de 1998.

– Y. Kohayakawa proferiu proferiu uma palestra convidada, intitulada On

Essentially Infinite Colourings of Graphs (50 minutos).

15. 2a. Escola Brasileira de Probabilidade, Barra de Sahi, SP, 2 a 7 de agosto

de 1998.

– Y. Kohayakawa proferiu a palestra Random and Pseudorandom Structures in Combinatorics and Theoretical Computer Science, palestra convidada (40 minutos). Participação financiada pelos organizadores.

16. ICM’98 – International Congress of Mathematicians, Berlin, RFA, 18–27 de

agosto/98.

– Participantes: C.G. Fernandes, Y. Kohayakawa e Y. Wakabayashi. To-

dos receberam auxílio dos organizadores.

17. Summer School on Probabilistic Methods for Algorithmic Discrete Mathe-

matics, Montpellier, França, 17 a 28 de agosto de 1998.

– Y. Kohayakawa proferiu duas aulas intituladas An Introduction to Pseudorandom Graphs and Szemerédi’s Regularity Lemma. Participação financiada pelos organizadores.

18. IX CLAIO – Congresso Latino-iberoamericano de Investigación Operativa,

Buenos Aires, Argentina, 2–4 de setembro/98.

– C.G. Fernandes apresentou o trabalho Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width. Financiado pelo pronex.

– Y. Wakabayashi apresentou o trabalho The Complexity of Computing Medians of Relations. Fez parte do Comitê de Programa. Financiado pelo pronex.

19. The DIMACS–IAS Workshop on Randomized and Derandomized Algorithms for Discrete Structures, Institute for Advanced Study, Princeton, NJ, EUA, 2 a 4 de novembro de 1998.

– Y. Kohayakawa proferiu a palestra Embeddings of Small Graphs in

Sparse Regular Graphs. Custos locais cobertos pelo evento.

20. Paul Erdős and his Mathematics, Budapeste, 4 a 11 de julho de 1999.

– Y. Kohayakawa proferiu uma palestra convidada, intitulada The Size-Ramsey Number of Graphs of Bounded Degree. Participação financiada em parte pelo pronex.

21. SODA’00 – 8^{th} Annual ACM-SIAM Symposium on Discrete Algorithms, San

Francisco-CA (EUA), 9–11 de janeiro/2000.

– J.C. de Pina apresentou o trabalho A New for the Carathéodory rank of the bases of a matroid. Participação financiada pelo pronex.

22. LATIN 2000 – Fourth Latin American Symposium on Theoretical INformatics, Punta del Este, Uruguay, 10–14 de abril/2000. Simpósio internacional dedicado à teoria da computação. Participaram vários membros do grupo. Y Wakabayashi fez parte do Comitê de Programa; e participou como co-autora de um trabalho.

– Y. Kohayakawa proferiu uma palestra convidada, intitulada Algorithmic Aspects of Regularity. Participação financiada em parte pelo evento.

– Y. Kohayakawa apresentou o trabalho Equivalent Conditions for Regu-

larity. Participação financiada em parte pelo evento.

23. CIRM/DONET Graph Theory Workshop, Levico, Trento, Itália, 6–10 de

maio/2000.

– Participante: J.C. de Pina. Participação financiada pelo próprio bolso.

24. ISMP2000 – XVII International Symposium on Mathematical Programming,

Atlanta, Georgia, EUA, 7–11 de agosto de 2000.

– C.G. Fernandes apresentou o trabalho The Chinese Postman and the Minimum Circuit Problem on Mixed Graphs. Participação financiada pelo pronex.

– J.C. de Pina apresentou o trabalho Improved Bound for the Carathéodory Rank of the Bases of a Matroid. Participação financiada pelo pronex.

– Y. Wakabayashi apresentou o trabalho A Hybrid Algorithm for the One-dimensional Cutting Stock Problem. Participação financiada pelo pronex.

5.2. Eventos no país.

1. III Oficina do Projeto ProComb, 29–30 de abril/97, IME-USP, SP. – O. Lee apresentou o trabalho Cobertura de Circuitos em Grafos Mistos.

2. Oficina do PCE, 16–17 de dezembro/97, IME-USP, SP.

3. XXI Colóquio Brasileiro de Matemática, 21–25 de julho/97. Rio de Janeiro,

RJ. Y. Kohayakawa organizou a Sessão de Combinatória.

– C.E. Ferreira apresentou o trabalho Decomposing Matrices into Blocks – C.G. Fernandes apresentou o trabalho Multicortes em Árvores de Grau

Limitado

4. XX Congresso de Matemática Aplicada e Computacional – II Oficina Nacional de Problemas de Cortes e Empacotamentos, setembro/97, Gramado, RS.

– F.K. Miyazawa apresentou o trabalho Approximation Algorithms for

Packing Small Items.

5. Workshop on Probabilistic Methods in Combinatorics and Theoretical Computer Science, 27 de abril a 1 de maio de 1998, Ubatuba, SP. Participaram C.G. Fernandes, Y. Kohayakawa, e J. Donadelli Jr. Apresentações informais de problemas foram feitas por C.G. Fernandes e Y. Kohayakawa. Veja mais detalhes na Seção 7.2.

6. I Encontro Regional de Matemática Aplicada e Computacional, 10–12 de

junho/98, São José do Rio Preto, SP.

– C.E. Ferreira apresentou o minicurso Planos de Corte Faciais e a Re-

solução de problemas de Otimização Combinatória.

7. XII Escola de Computação, 20–24 de julho/98, Rio de Janeiro, RJ.

– Participantes: C.E. Ferreira, C.G. Fernandes, J.C. de Pina, M.A.M.C.

Gurgel, Y. Kohayakawa e Y. Wakabayashi.

8. Congresso da Sociedade Brasileira de Computação, 3–5 de agosto/98, Belo

Horizonte, MG.

– Participante: C.E. Ferreira.

9. WPOC — Workshop em Paralelismo e Otimização Combinatória, 28 de

setembro/98, Búzios.

– M.A. Stefanes apresentou o trabalho Algoritmo Assíncrono para Flo-

resta Geradora Mínima.

10. XXII Colóquio Brasileiro de Matemática, 26–30 de julho/99. Rio de Janeiro,

RJ. Y. Kohayakawa organizou a Sessão de Combinatória.

– Y. Wakabayashi apresentou o trabalho Empacotamento de Quadrados em Quadrados

– Y. Kohayakawa proferiu uma palestra de divulgação (palestra convidada), intitulada Da Teoria Combinatória dos Números à Busca na Internet. Paticipação financiada pelos organizadores.

– Participantes: A. Mandel, C.G. Fernandes, J.C. de Pina, J. Soares,

Y. Kohayakawa e Y. Wakabayashi.

11. II Workshop do Projeto ProNEx “Complexidade de Estruturas Discretas”, Hotel do Bosque, Angra dos Reis, RJ, Brazil, de 29 novembro a 3 dezembro de 1999. Financiado pelo pronex.

– Y. Kohayakawa apresentou a palestra Grafos Pseudo-aleatórios

– Participantes: A. Mandel, C.E. Ferreira, C.G. Fernandes, J.C. de Pina,

J. Soares, P. Feofiloff, Y. Kohayakawa e Y. Wakabayashi.

12. Workshop on Combinatorics and Discrete Structures, Instituto de Computação, UNICAMP, Campinas, SP, Brazil, 2 a 4 agosto de 1999. Financiado pelo pronex.

– C.G. Fernandes apresentou o trabalho Edge-coloring series-parallel multigraphs

– Participantes: A. Mandel, C.E. Ferreira, C.G. Fernandes, J.C. de Pina,

J. Soares, Y. Kohayakawa e Y. Wakabayashi.

13. III Workshop in Combinatorics and Discrete Structures Hotel Wembley Inn,

Ubatuba, SP, 16 a 20 abril de 2000. Financiado pelo pronex.

– J.C. de Pina apresentou o trabalho Improved Bound for the Carathéodory Rank of the Bases of a Matroid

– Participantes: A. Mandel, C.E. Ferreira, C.G. Fernandes, J.C. de Pina,

Y. Kohayakawa e Y. Wakabayashi.

14. First Latin American Congress of Mathematicians, IMPA, Rio de Janeiro,

31 de julho a 4 de agosto de 2000.

– Y. Kohayakawa proferiu uma palestra convidada na Sessão de Otimização e Combinatória.

5.3. Estágios no exterior e visitas curtas.

1. Carlos E. Ferreira, ZIB-Berlin, 30 de agosto/1997 a 5 de setembro/97. Financiado pelo projeto ProBRAL 001/94 (capes-daad).

2. Cristina G. Fernandes.

• Georgia Tech, 24–27 de junho/1998. Financiada pelo cnpq.

• Georgia Tech, janeiro e fevereiro de 1999. Financiada pela fapesp.

• Humboldt-Universität zu Berlin, 9 semanas, a partir de 15 de dezembro de 1999. Financiada pelo projeto ProBRAL 089/99 (capes-daad).

• Georgia Tech, 6–19 de agosto/2000. Financiada pelo ProNEx 107/97 (mct/finep).

• Illinois Institute of Technology, 20–26 de agosto/2000. Financiada pelo

I.I.Tech. Convite de G. Călinescu.

3. Yoshiharu Kohayakawa.

• AT&T Labs Research, outubro de 1996 (3 semanas). Financiado pela AT&T. Convite de R.L. Graham.

• University of Memphis, 4 meses, a partir de 15 de janeiro de 1997. Financiado pela U. of Memphis. Convite de B. Bollobás.

• Humboldt-Universität zu Berlin, 7 semanas, a partir de 4 de janeiro de 1997. Financiado pelo projeto ProBRAL 026/95 (capes-daad).

• DIMACS, janeiro e fevereiro 1999, financiado por DIMACS e Rutgers.

• Emory University, várias visitas, para trabalho conjunto com V. Rödl.

4. Yoshiko Wakabayashi

• ZIB-Berlin, outubro a dezembro/96. Financiado pelo projeto ProBRAL 001/94 (capes-daad).

• Institut Pasteur, de 15 de janeiro a 26 de fevereiro de 2000. Financiado pelo Projeto no. 272/99-II (capes-cofecub).

6. Visitantes

Durante o período, a nossa equipe recebeu a visita de vários pesquisadores estrangeiros. Mesmo devido à longa duração, a visita do prof. Bruce Reed merece especial destaque.

1. Dr. Ralf Borndörfer, ZIB, Berlin (dezembro 1996). [capes-daad - C.E. Ferreira]

2. Professor Bruce Reed, CNRS, Paris (maio/novembro 1997). [Proc. 96/12111– 4 - fapesp - Y. Kohayakawa]

3. Professor Vojtěch Rödl, Emory University, Atlanta (junho 1997). [usp - Y. Kohayakawa]

4. Professor Endre Szemerédi, Rutgers University, NJ (junho 1997). [usp - Y. Kohayakawa]

5. Dr. Bernd Kreuter, Humboldt-Universität, Berlin (agosto/setembro 1997). [capes-daad - Y. Kohayakawa]

6. Professor Laurence Wolsey, CORE Louvain (3–5 de agosto de 1997). [C.E. Ferreira]

7. Professor Gerhard Wäscher, Martin-Luther-Universität, Halle-Wittenberg (17–19 de setembro 1997) [cnpq - Projeto PCE - Y. Wakabayashi]

8. Professor Hanno Lefmann, Universität Dortmund (outubro 1997). [usp - Y. Kohayakawa]

9. Professor András Sebö, Laboratoire Leibniz-IMAG, Grenoble (1–2 de dezembro 1997). [ime-usp]

10. Professor Robin Thomas, Georgia Tech, Atlanta (abril 1998). [Proc. 97/14469-6 - fapesp - C.G. Fernandes]

11. Professor Pavel Pudlák, Praga (abril/maio 1998). [usp e pronex - Y. Kohayakawa] 12. Professor Zoltán Füredi, Urbana-Champaign e Budapest (abril/maio 1998).

[usp - Y. Kohayakawa]

13. Os professores N. Alon, L. Devroye, P.E. Haxell, J.H. Kim, e P. Tetali participaram do Workshop on Probabilistic Methods in Combinatorics and Theoretical Computer Science, Ubatuba, SP, 27 de abril a 1 de maio de 1998. O evento cobriu as despesas locais dos participantes (veja Seção 7.2).

14. Professor Daniel H. Younger, University of Waterloo (6 de julho de 1998). [P. Feofiloff]

15. Professor Kristina Vuskovic, University of Kentucky (13–14 de agosto de 1998). [ime-usp- C.G. Fernandes]

16. Professor John Beasley, Imperial College (9-10 de setembro 1998). [cnpq - projeto PCE - C.E. Ferreira]

17. Dra. Marie-France Sagot, Institut Pasteur (24 de janeiro a 14 de fevereiro de 1999). [capes-cofecub- Y. Wakabayashi]

18. Professor Martin Grötschel, TU-Berlin (6 a 7 de maio de 1999). [ime-usp-Y. Wakabayashi]

19. Professor C.Q. Zhang, West Virginia University (5 a 7 de agosto de 1999). [ime-usp- Y. Wakabayashi]

20. Dr. Anusch Taraz, Humboldt-Universität, Berlin (setembro de 1999). [capesdaad- Y. Kohayakawa]

21. Dr. Daniel Panario, Universidade de Toronto (13 a 17 de outubro de 1999). [pronexComplexidade de Estruturas Discretas - Y. Kohayakawa]

22. Professor Alfredo Viola, Universidade da República, Uruguai (13 a 17 de outubro de 1999). [pronex Complexidade de Estruturas Discretas - Y. Kohayakawa]

23. Professor Marcos Kiwi, Universidade de Chile (13 a 17 de outubro de 1999). [pronex Complexidade de Estruturas Discretas - Y. Kohayakawa]

24. Dr. Hein van der Holst, Centrum voor Wiskunde en Informatica (20 de agosto a 19 de outubro de 2000). [Financiamento em julgamento na fapesp - J.C. de Pina]

7. Eventos

7.1. Seminários. Estes seminários vem ocorrendo regularmente desde 1995, com a participação de membros do nosso grupo de pesquisa e pesquisadores visitantes.

7.1.1. Segundo semestre de 1997.

1. The Complexity of Some Problems on Very Sparse Graphs – Bernd Kreuter, HU Berlin, 22 de agosto.

2. Recent Issues on Cutting and Packing – Gerhard Wäscher, Martin-Luther-Universität, Halle-Wittenberg, 19 de setembro.

3. Multicortes em Árvores de Grau Limitado – Cristina G. Fernandes, ime-usp, 10 de outubro.

4. Finding k-Edge-Connected Spanning Subgraphs: a Better Analysis – Cristina G. Fernandes, ime-usp, 17 de outubro.

5. Independent Sets in Graphs and Hypergraphs and Their Applications – Hanno Lefmann, Universität Dortmund, RFA, 28 de outubro.

6. Um Algoritmo Melhor para Encontrar Subgrafos Planares – Cristina G. Fernandes, ime-usp, 31 de outubro.

7. Computação Quântica – Cristina G. Fernandes, ime-usp, 7 de novembro.

8. Um Algoritmo de Aproximação para Subgrafos Planares Pesados – Cristina G. Fernandes, ime-usp, 21 de novembro.

7.1.2. Primeiro semestre de 1998. 1. A Conjectura de Woodall – Orlando Lee, ime-usp, 6 de março.

2. Multicortes em Grafos de Grau Limitado – Cristina G. Fernandes, ime-usp, 13 de março.

3. Problemas em aberto – apresentação de alguns problemas em aberto feita pelos participantes do seminário, 20 de março.

4. O Teorema de Erdős e Rado e Colorações Essencialmente Infinitas – Yoshiharu Kohayakawa, ime-usp, 27 de março.

5. Hypergraphs in Codes, Designs and in Combinatorial Geometry – Zoltán Füredi, Urbana-Champaign (Illinois) e Budapest, 6 de maio.

6. Conjectura de Woodall: o Caso dos Grafos com Conexão Fonte-Sorvedouro – Paulo Feofiloff, ime-usp, 15 de maio e 22 de maio.

7. Potentials in Undirected Graphs and Planar Multiflows – Mario Leston, ime-usp, 5 de junho.

8. The 3-Flow Conjecture for Graphs – D.H. Younger, University of Waterloo, 6 de julho.

7.1.3. Segundo semestre de 1998.

1. Progressos Recentes sobre Decomposição do Hipercubo em Ciclos Hamiltonianos – Kunio Okuda, ime-usp, 7 de agosto.

2. Progressos Recentes sobre Decomposição do Hipercubo em Ciclos Hamiltonianos - Parte 2 – Carlos Eduardo Rodrigues Alves, ime-usp, 7 de agosto.

3. Decomposition Theorem and Recognition Algorithm for Even-Hole-Free Graphs – Kristina Vuskovic, University of Kentucky (EUA), 14 de agosto.

4. Scheduling Aircraft Landings – John Beasley, Imperial College (Londres), 9 de setembro.

5. Examples from Infinitary Combinatorics – Piotr Koszmider, ime-usp, 18 e 25 de setembro.

7.1.4. Primeiro semestre de 1999.

1. Monotonicidade de Buscas em Grafos – Carlos Eduardo Rodrigues Alves, ime-usp, 12 de março.

2. Aresta-Coloração de Multigrafos Série-Paralelos – Cristina Gomes Fernandes, ime-usp, 19 de março.

3. Uma relação minimax envolvendo decomposições em orelhas e pesos conservativos – Mario Leston, ime-usp, 26 de março.

4. Applications of Combinatorial Online Optimization – Martin Groetschel, TU-Berlin, 7 de maio.

7.1.5. Segundo semestre de 1999.

1. On Circuit Decompositions of Graphs – C.Q. Zhang, West Virginia University, 6 de agosto.

2. O Problema da Cobertura Mínima por Circuitos – Orlando Lee, 19 de agosto.

3. O problema de corte unidimensional e a conjectura MIRUP – Glauber Cintra, 26 de agosto.

4. Algoritmos de aproximação para tree-alignment – Estela Maris Rodrigues, 2 de setembro.

5. Random maximal H-free graphs – Anusch Taraz, Humboldt-University Berlin, 16 de setembro.

6. O Problema do Balance Máximo – Liliane Rose Benning Salgado, 23 de setembro.

7. Seqüenciamento de DNA por montagem de fragmentos: um estudo comparativo de suas ferramentas – Said Sadique Adi, 30 de setembro.

8. On the jump number – Hyung Chan Jung, Korean University of Technology and Education, 1 de outubro.

9. Grafos Aleatórios: Leis Zero-Um, Jogos de Ehrenfeucht e o Teorema de Shelah-Spencer – Alexandre Scalzitti, 14 de outubro.

10. Um resultado na Teoria de Ramsey – Márcio Grossi de Almeida, 22 de outubro.

11. Grafos cobertos por emparelhamentos: propriedades e problemas – Marcelo Henriques de Carvalho, UFMS, 26 de novembro.

7.1.6. Primeiro semestre de 2000.

1. Caracterizando Grafos de Seymour: preliminares – Mario Leston Rey, imeusp, 21 de março.

2. Caracterizando Grafos de Seymour – Mario Leston Rey, ime-usp, 28 de março.

3. Uma prova curta para o Teorema min-max de Mader para o número máximo de S-caminhos disjuntos – José Coelho de Pina, ime-usp, 29 de junho e 6 de julho.

7.2. Oficina.

• Workshop on Probabilistic Methods in Combinatorics and Theoretical Com-

puter Science, Ubatuba/SP, 27 de abril a 1 de maio de 1998.

Durante esta oficina extremamente informal, vários dos participantes apresentaram diversos problemas em aberto ou trabalho de pesquisa que vinham realizando relacionados com estruturas aleatórias ou combinatórias em geral. A oficina foi uma ótima ocasião para colaboração.

– Participantes: N. Alon, L. Devroye, J. Donadelli Jr., C.G. Fernandes, Z. Füredi, P.E. Haxell, J.H. Kim, Y. Kohayakawa, L.R. Moura, D. Panario, P. Pudlák, B. Reed, P. Tetali, A. Viola.

Destacamos novamente que 3 destes participantes são renomados pesquisadores que proferiram palestras em Congressos Internacionais de Matemáticos (Alon, Füredi e Pudlák) e um deles (Kim) foi o ganhador da Medalha Fulkerson em 1997.

O idealizador deste encontro foi o professor visitante Bruce Reed, a quem devemos a realização de um encontro de tal qualidade. A organização local ficou a cargo de C.G. Fernandes e Y. Kohayakawa.

7.3. Minicursos e eventos especiais.

1. Dia da Combinatória, ime-usp, 1 de dezembro de 1997.

Neste dia, realizamos uma série de palestras proferidas por professores visitantes.

– On the Jump Number of Ordered Sets – Klaus Reuter, Universidade de Hamburgo, Alemanha.

– Alguns Resultados e Conjecturas em Contagem de Recobrimentos por Dominós – Nicolau Corção Saldanha, Pontifícia Universidade Católica do Rio de Janeiro.

– Flows, View-obstructions and the Lonely Runner – András Sebö, La-

boratoire Leibniz-IMAG, Grenoble.

2. Lectures on Tree-decompositions, Permanents, Pfaffian Orientations and

Even Directed Circuits.

O minicurso, dado pelo Prof. Robin Thomas do Georgia Institute of Technology, consistiu de uma série de 6 palestras sobre largura arbórea e problemas correlatos. As palestras ocorreram nos dias 1, 3, 6, 7, 8 e 13 de abril de 1998.

3. Uso de Bases de Gröbner em Combinatória.

O Prof. Arnaldo Mandel, do nosso grupo de pesquisa, preparou e apresentou um minicurso sobre bases de Gröbner. As aulas ocorreram nos dias 9, 16, 23, 30 de outubro e 6 de novembro de 1998, como parte das atividades semanais dos seminários do grupo.

4. Dia de Otimização e Combinatória, ime-usp, 19 de novembro de 1998.

Neste dia, foram realizadas uma série de palestras proferidas por professores visitantes.

– Localização de ERB e Alocação de Canais em Sistemas Móveis Celulares – Geraldo Robson Mateus, UFMG.

– Cem Horas de Solidão – Manoel Lemos, UFPE.

– Packing Identical Boxes into a Container – Sóstenes Lins, UFPE.

5. Dia de Algoritmos e Combinatória, ime-usp, 15 de outubro de 1999.

Neste dia, foram realizadas uma série de palestras proferidas por professores visitantes.

– On Combinatorial Aspects of Linear Probing Hashing – Alfredo Viola, Universidad de la Republica, Uruguay.

– Largest and Smallest Size of Components in Decomposable Structures – Daniel Panario, University of Toronto.

– Min-Max-Boundary Domain Decomposition – Marcos Kiwi, Universidad de Chile, Chile.

8. Auxílios Vigentes

8.1. Bolsas. Mencionamos as bolsas de pesquisa, doutorado, mestrado e iniciação científica obtidas pelos participantes desta equipe.

8.1.1. Bolsas de pesquisa.

– Carlos Eduardo Ferreira - Bolsa de Auxílio a Pesquisa do cnpq, nível 2B.

– Cristina Gomes Fernandes - Bolsa de Auxílio a Pesquisa do cnpq, nível 2C.

– Yoshiharu Kohayakawa - Bolsa de Auxílio a Pesquisa do cnpq, nível 1C.

– Yoshiko Wakabayashi - Bolsa de Auxílio a Pesquisa do cnpq, nível 1B.

8.1.2. Bolsas de doutorado.

– Estela Maris Rodrigues [Y. Wakabayashi], bolsa do cnpq (Proc. 574226/97-4) desde março de 1997.

– Glauber Ferreira Cintra [Y. Wakabayashi], bolsa do cnpq desde outubro de 1999.

– Jair Donadelli Júnior [Y. Kohayakawa], bolsa do cnpq desde janeiro de 1998.

– Liliane R.B. Salgado [Y. Wakabayashi], bolsa da fapesp (Proc. 98/02407-9) desde agosto de 1998.

– Marco Aurélio Stefanes [J. Soares], bolsa da fapesp (Proc. 98/06327-0) desde agosto de 1998.

– Orlando Lee [Y. Wakabayashi], bolsa da capes de março de 1995 a fevereiro de 1999.

8.1.3. Bolsas de mestrado.

– Carlos R. Pantaleon Dionisio [J.C. de Pina], bolsa do cnpq de março de 1996 a fevereiro de 1997.

– Aritanan Borges Garcia Gruber [C.E. Ferreira], bolsa cnpq de março de 1997 a fevereiro de 1999.

– Said Sadique Adi [C.E. Ferreira], bolsa cnpq de março de 1998 a fevereiro de 2000.

– Alexandre Noma [C.G. Fernandes], bolsa fapesp desde agosto de 2000.

– Cássio Polpo de Campos [C.E. Ferreira], bolsa fapesp desde março de 1999.

– Eduardo Garcia de Freitas [C.E. Ferreira], bolsa fapesp desde março de 1999.

– Gordana Manic [P. Feofiloff], bolsa capes desde agosto de 1999.

– Luiz Carlos Rozante [J. Soares], bolsa cnpq desde março de 1999.

– Ronney Rodeger Sales de Castro [C.G. Fernades], bolsa capes desde março de 1999.

– Shigueo Isotani [J.C. de Pina], bolsa capes desde março de 2000.

8.1.4. Bolsas de iniciação científica.

– Cassio Polpo de Campos [C.E. Ferreira], bolsa fapesp (Proc. 97/09522-5) de fevereiro a dezembro/98.

– Eduardo Garcia de Freitas [C.E. Ferreira], bolsa fapesp (Proc. 97/09522-5) de fevereiro a dezembro/98.

– Rodrigo Nonamor Pereira Mariano de Souza [C.E. Ferreira], bolsa PIBIC-cnpq desde maio/98.

– Thiago Teixeira Santos [C.E. Ferreira], bolsa PIBIC-cnpq desde fevereiro/98.

8.2. Projetos integrados. Os membros da equipe deste projeto da fapesp participa(ra)m dos seguintes projetos:

• Projeto de intercâmbio internacional capes-daad: Problemas de Empacotamento e Partição de Grafos e Hipergrafos – ProBRAL 001/94. Este é um projeto de intercâmbio entre o Brasil e a Alemanha. Instituições envolvidas: ZIB–Berlin (coordenador: M. Grötschel), e IME–USP (coordenadora: Y. Wakabayashi). Participantes brasileiros: C.E. Ferreira e Y. Wakabayashi. Vigência: outubro de 1994 a fevereiro de 1998. Página na Teia:

    http://www.ime.usp.br/~cef/probral/

• Projeto de intercâmbio internacional capes-daad: Combinatória Extremal e Métodos Probabilísticos – ProBRAL 026/95. Este é um projeto de intercâmbio entre o Brasil e a Alemanha. Instituições envolvidas: Humboldt-Universität zu Berlin (coordenador: H.J. Prömel), e IME–USP (coordenador: Y. Kohayakawa). Participantes brasileiros: Y. Kohayakawa e J.A.R. Soares. Vigência: setembro de 1995 a agosto de 1998. Página na Teia:

    http://www.ime.usp.br/~yoshi/index_DAAD.html

• Projeto de intercâmbio internacional capes-daad: Teoria dos Grafos: Aspectos Assintóticos e Algorítmicos – ProBRAL 089/99. Este é um projeto de intercâmbio entre o Brasil e a Alemanha. Instituições envolvidas: Humboldt-Universität zu Berlin (coordenador: H.J. Prömel), e IME–USP (coordenador: Y. Kohayakawa). Participantes brasileiros: Y. Kohayakawa, C.G. Fernandes, J.C. de Pina, e J. Donadelli (aluno de doutorado). Vigência: março de 1999 fevereiro de 2001 (extensão pleiteada para o terceiro ano). Página na Teia:

  http://www.ime.usp.br/~jair/projDAAD.html

• Projeto Temático Multi-institucional do cnpq: Problemas de Cortes & Empacotamentos e Correlatos – ProTeM-CC-III. Período: outubro/96 a outubro/98. Coordenador: H. Yanasse. Participantes da equipe: C.E. Ferreira, Y. Wakabayashi. Página na Teia:

  http://www.ime.usp.br/~cef/pce/

• Projeto dentro do programa de cooperação internacional capes-cofecub: Algoritmos para Análise de Genomas. Coordenador do lado francês: M. Crochemore; coordenadora do lado brasileiro: Y. Wakabayashi. Início em janeiro de 1999. Página na Teia:

  http://www.ime.usp.br/~yw/capes/capes-cofecub/

• Projeto dentro do programa de cooperação internacional cnpqnsf: Combinatória Extremal e Métodos Probabilísticos. Coordenador do lado americano: V. Rödl; coordenador do lado brasileiro: Y. Kohayakawa. Início em agosto de 1999; vigência de 2 anos. Participantes brasileiros: Y. Kohayakawa, 2 alunos de doutorado, e 1 aluno de mestrado; participantes americanos: V. Rödl (PI), e os co-PI L. Thoma, J. Skokan, B. Nagle, e D. Duffus. Veja

  https://www.fastlane.nsf.gov/servlet/showaward?award=0072064

8.3. Núcleo de Excelência. A equipe deste projeto temático faz parte de um núcleo de excelência do programa pronex do mct–finep:

Complexidade de Estruturas Discretas (projeto no. 107/97).

Este núcleo tem apoio no período de janeiro de 1998 a dezembro de 2001. Coordenador: Y. Kohayakawa. Página na Teia:

http://www.ime.usp.br/~yoshi/pronex/

9. Prêmios e Honrarias

9.1. Teses e dissertações premiadas.

– Marko Loparic [C.E. Ferreira] – Dissertação de mestrado premiada em 2^{o.} lugar no CTD’97 (Concurso de Teses e Dissertações) promovido pela SBC (Sociedade Brasileira de Computação). Título da dissertação: Uma aplicação do Método de Branch and Cut a um Problema de Roteamento de Veículos – ime-usp, janeiro/96.

– Flávio Keidi Miyazawa [Y. Wakabayashi] – Tese de doutorado premiada em 1^{o.} lugar no CTD’98 (Concurso de Teses e Dissertações) promovido pela SBC (Sociedade Brasileira de Computação). Título da tese: Algoritmos de Aproximação para Problemas de Empacotamentos – ime-usp, novembro/97.

– Glauber Ferreira Cintra [Y. Wakabayashi] – Dissertação de mestrado premiada em 1^{o.} lugar no VI Concurso CLEI-UNESCO de Teses de Maestria (de âmbito latino-americano). Título da dissertação: Algoritmos Híbridos para Problemas de Corte Unidimensional – ime-usp, julho/98.

9.2. Academia Brasileira de Ciências. Y. Kohayakawa foi eleito Membro Associado da Academia Brasileira de Ciências em 16 de novembro de 1998.

10. Outras Atividades

10.1. Miscelâneas.

– Y. Kohayakawa organizou a Sessão de Combinatória no XXI Colóquio Brasileiro de Matemática, 21–25 de julho/97, Rio de Janeiro.

– Y. Kohayakawa participou do Comitê de Programa da XI Escola de Computação, 21–24 de julho/98, Rio de Janeiro.

– Y. Kohayakawa participou do Comitê de Programa do LATIN’98 – Third Latin American Symposium on Theoretical Informatics, 20–24 de abril/98, Campinas.

– Y. Kohayakawa é membro da Coordenação de Área de Matemática e Ciência da Computação da fapesp desde dezembro de 1998.

– Y. Kohayakawa é membro do Comitê Assessor de Ciência da Computação do cnpq no biênio 1999/2000.

– Y. Wakabayashi participou do Comitê de Programa do IX CLAIO – Congresso Latino-iberoamericano de Investigación Operativa, 2–4 de setembro/98, Buenos Aires, Argentina.

– Y. Wakabayashi foi membro do Comitê Assessor de Ciência da Computação do cnpq no biênio 1997/1998.

– Y. Kohayakawa organizou a Sessão de Combinatória no XXII Colóquio Brasileiro de Matemática, 25–30 de julho/99, Rio de Janeiro.

– Y. Wakabayashi participou do Comitê de Programa do LATIN’2000 – Fourth Latin American Symposium on Theoretical Informatics, 9–15 de abril/2000, Punta del’Este, Uruguai.

– C.E. Ferreira e Y. Kohayakawa participaram da organização da Escola de Computação 2000, 24 a 28 de julho de 2000, São Paulo.

10.2. Atividades administrativas atuais/recentes. Enumeramos aqui alguns cargos administrativos no ime-usp assumidos pelos membros da equipe.

1. Arnaldo Mandel, chefe do Departamento de Ciência da Computação, administrador da rede do ime-usp.

2. Carlos Eduardo Ferreira, presidente da Comissão de Graduação do ime-usp.

3. Cristina Gomes Fernandes, presidente da Comissão de Admissão e Bolsas do Programa de Pós-graduação em Ciência da Computação do ime-usp.

4. José Coelho de Pina Júnior, membro da Comissão de Horários e da Comissão dos Cursos de Verão do ime-usp.

5. Yoshiharu Kohayakawa, presidente da Comissão de Pesquisa do ime-usp até junho de 2000.

6. Yoshiko Wakabayashi, coordenadora do Programa de Pós-graduação em Ciência da Computação do ime-usp.

11. Conclusão e Análise Crítica

Tecemos aqui uma apreciação do desempenho de nossa equipe nesses últimos 4 anos.

Primeiramente observamos que a equipe não cumpriu os prazos para o envio dos relatórios e da prestação de contas. Houve uma certa inércia a este respeito, sobre a qual não temos nenhuma justificativa muito plausível.

Esperávamos um maior número de publicações no período; de fato, na opinião do coordenador, os números são bons mas não são excelentes. A equipe conta com alguns jovens pesquisadores (com doutorado de 1994, 1995 e 1997), que começaram recentemente a adquirir uma certa senioridade em pesquisa. Com o desenvolvimento destes pesquisadores, acreditamos que teremos uma equipe com uma produção científica mais volumosa em um futuro não muito distante.

Apesar de nossas estatísticas não serem de particular destaque em termos internacionais, acreditamos que é relevante a qualidade dos periódicos em que nossos trabalhos foram publicados (veja Seções 1.2 e 3). De fato, os veículos em que publicamos os nossos trabalhos são, em grande maioria, os periódicos mais tradicionais da área, sugerindo um reconhecimento internacional de nosso trabalho. A nossa inserção na comunidade internacional também pode ser vista pela nossa forte colaboração com pesquisadores e centros internacionais de excelência.

Desempenhamos um papel importante na formação de alunos (veja Seção 4), em todos os níveis. Três deles receberam premiações pelas suas dissertações e teses (veja Seção 9). Um de nossos ex-alunos é membro hoje de um dos melhores centros em ciência da computação no país. Um outro recém-doutor recebeu convite para realizar pós-doutorado na Georgia Institute of Technology, um excelente centro de pesquisa no exterior (está pleiteando uma bolsa para isso).

Acreditamos que, com o apoio fundamental da fapesp e de nossos outros projetos de pesquisa, poderemos continuar contribuindo de forma decisiva para o desenvolvimento desta área de pesquisa no país e também poderemos consolidar a nossa posição na comunidade internacional.