Complexity of Discrete Structures

Projeto ProNEx 107/97 - MCT/CNPq

Proc. CNPq 664107/1997-4 and Proc. CNPq 466051/2001-8

Sponsored by the Ministry of Science and Technology (MCT) through Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) under "Programa de Apoio a Núcleos de Excelência".

On the news

• João Meidanis no Estado de São Paulo: capa e matéria (arquivos PDF).

Prizes and honours

• Sóstenes Luiz Soares Lins é eleito em dezembro de 2001 membro titular da Academia Brasileira de Ciências.
• Cid Carvalho de Souza recebe o Prêmio Zeferino Vaz de 2001 do IC/UNICAMP.
• Yoshiharu Kohayakawa é eleito em novembro de 2000 membro titular da Academia Brasileira de Ciências (membro associado desde 1998).
• Cláudio Leonardo Lucchesi recebe Prêmio Santista [Fundação Santista | Estadão]
• Covas confere o Trófeu e a Medalha do Mérito Científico e Tecnológico aos 35 laboratórios e aos 192 cientistas que participaram do projeto Genoma Xyllela, incluindo os coordenadores de bioinformática, João Meidanis e João Setubal.

Events organized

• Workshop on Approximation Algorithms and Graph Theory, Hotel Rancho Silvestre, Embú/SP, 5 - 7 September 2004.
• Workshop on Combinatorics, Algorithms, and Applications, Ubatuba, SP, Brazil, 1 - 5 September 2003.
• Workshop on Combinatorics and Optimization, Hotel Vale das Vinhas, Jundiai/SP, 14 - 16 February 2003
• Workshop in Combinatorics and Optimization, Hotel Fazenda Santa Helena, Mairiporã, SP, Brazil, 14 - 16 November 2002
• Extended Workshop on Combinatorics, São Paulo, Ubatuba, and Rio de Janeiro, 4 - 14 March 2002
• Workshop on Approximation Algorithms, Hotel Simon, Itatiaia, RJ, Brazil, 7 - 11 October 2000
• III Workshop in Combinatorics and Discrete Structures, Hotel Wembley Inn, Ubatuba, SP, Brazil, 16 - 20 April 2000
• Workshop Mambucaba, Hotel do Bosque, Angra dos Reis, RJ, Brazil, 29 November - 3 December 1999
• Workshop on Combinatorics and Discrete Structures, Instituto de Computação, UNICAMP, Campinas, SP, Brazil, 2 - 4 August 1999 (fotos)

Members of the Group

1. Nalvo Franco de Almeida <nalvo@dct.ufms.br>
2. Marcelo Henriques de Carvalho <mhc@dct.ufms.br>
3. Márcia Rosana Cerioli <cerioli@cos.ufrj.br>
4. Ricardo Dahab <rdahab@dcc.unicamp.br>
5. Paulo Feofiloff <pf@ime.usp.br>
6. Cristina Gomes Fernandes <cris@ime.usp.br>
7. Carlos Eduardo Ferreira <cef@ime.usp.br>
8. Celina M. H. Figueiredo <celina@cos.ufrj.br>
9. Cleide S. Martins Gomes <cleide@dmat.ufpe.br>
10. Katia Silva Guimarães <katia@cin.ufpe.br>
11. Sulamita Klein <sula@cos.ufrj.br>
12. Yoshiharu Kohayakawa <yoshi@ime.usp.br>
13. Manoel Lemos <manoel@dmat.ufpe.br>
14. Sóstenes Luiz Soares Lins <sostenes@dmat.ufpe.br>
15. Cláudio Leonardo Lucchesi <lucchesi@dcc.unicamp.br>
16. Arnaldo Mandel <am@ime.usp.br>
17. Fábio H. Viduani Martinez <fhvm@dct.ufms.br>
18. João Meidanis <meidanis@dcc.unicamp.br>
19. Célia Picinin de Mello <celia@dcc.unicamp.br>
20. Flávio Keidi Miyazawa <fkm@dcc.unicamp.br>
21. José Coelho de Pina Jr. <coelho@ime.usp.br>
22. João Carlos Setubal <setubal@dcc.unicamp.br>
23. José Augusto R. Soares <jose@ime.usp.br>
24. Cid Carvalho de Souza <cid@dcc.unicamp.br>
25. Yoshiko Wakabayashi <yw@ime.usp.br>

Participating Institutions and Research Groups

• Grupo de Pesquisa em Combinatória, Departamento de Ciência da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo
• Instituto de Computação, Universidade Estadual de Campinas
• Departamento de Matemática e Departamento de Informática, Universidade Federal de Pernambuco
• Grupo de Pesquisa em Teoria de Grafos e Algoritmos, Departamento de Ciência da Computação e COPPE - Sistemas de Computação, Universidade Federal do Rio de Janeiro
• Departamento de Computação e Estatística, Universidade Federal de Mato Grosso do Sul

Main Research Interests

Publications of Group Members

Open Problems

Information on the Project

• The research project (in Portuguese, submitted in May 1997) [dvi.gz | ps.gz]
• Reports
  • Partial report (first year) [parte1.ps, parte2.ps | parte1.pdf, parte2.pdf (in Portuguese)]
  • Students (in Portuguese, 1998 edition) [dvi | ps | pdf]
  • Partial report (second year, in Portuguese) [pdf]
  • Students (in Portuguese, 1999 edition) [dvi | ps | pdf]
  • Partial report (third year, in Portuguese) [pdf]
  • Students (in Portuguese, 2000 edition)
  • Partial report (fourth year, in Portuguese) [pdf]
  • Students (in Portuguese, 2001 edition)
  • Partial report (fifth year, in Portuguese) [pdf]
  • Students (in Portuguese, 2002 edition)
  • Full report, 1998 to 2002 (FINEP version, in Portuguese) [PDF (610k) | PostScript (5.4M)]
  • Partial report (sixth year, in Portuguese) [pdf]
  • Students (in Portuguese, 2003 edition)
  • Students (in Portuguese, 2004 edition)
  • Final report (CNPq version, in Portuguese) [PDF (840k) | PostScript (5.2M)]

Upcoming (and Past) Events of Interest

• LATIN 2002 - Latin American Theoretical INformatics, Cancun, Mexico, April 3 to 6, 2002.
• Workshop Latino-Americano de Cliques em Grafos. Rio de Janeiro, April 17 to 19, 2002.
• Thematic Programme on Asymptotic Geometric Analysis, PIMS at the University of British Columbia, Summer 2002.
• ICM2002, International Congress of Mathematicians, Beijing, China, August 20-28, 2002.
• ALGO2002 (ESA2002/APPROX2002/WABI2002), 10th Annual European Symposium on Algorithms (deadline April 15), 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (deadline May 20), 2nd Workshop on Algorithms in Bioinformatics (deadline April 26) - University of Rome "La Sapienza", 17-21 September, 2002.
• Combinatorics, in Honour of Walter Deuber's 60th Birthday, Humboldt-Universität zu Berlin, 7th and 8th October 2002.
• Workshop on Extremal Graph Theory, a meeting dedicated to the 60th birthday of Miklós Simonovits, Budapest, June 16-20, Balaton, June 23-27, 2003.
• 9th Annual International Computing and Combinatorics Conference (COCOON'03), Big Sky, MT, USA, July 25-28, 2003. (Submission: February 7.)
• Combinatorics in Cambridge, in honour of Béla Bollobás on his 60th birthday, Cambridge, UK, 4 to 7 August 2003
• 18th International Symposium on Mathematical Programming (ISMP 2003), Technical University of Denmark, Copenhagen, Denmark, August 18-22, 2003. (Early registration: before April 30; abstract: May 31.)
• 6th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2003), and 7th. International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2003), 24-26 August 2003, Princeton University
• First Workshop on Approximation and Online Algorithms (WAOA 2003), 15 - 20 September 2003, Budapest, Hungary. (Deadline:June 30, 2003) ( + info)

Past Events of Interest

Information for Group Members