| Processo: | 05/53840-0 |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Data de Início da vigência: | 01 de setembro de 2005 |
| Data de Término da vigência: | 31 de agosto de 2006 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Pesquisador responsável: | Yoshiko Wakabayashi |
| Beneficiário: | Frederic Chataigner |
| Instituição Sede: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil |
| Vinculado ao auxílio: | 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas, AP.PRNX.TEM |
| Assunto(s): | Otimização combinatória Grafos |
| Palavra(s)-Chave do Pesquisador: | Algoritimos De Aproximacao | Empacotamento De Subgrafos | Grafos | Nao-Aproximabilodade | Otimizacao Combinatoria | Particao De Grafos |
Resumo A pesquisa será centrada no estudo de duas classes de problemas de otimização combinatória, com ênfase em seus aspectos algorítmicos e teóricos. Estamos interessados no desenvolvimento de algoritmos de aproximação e resultados sobre complexidade computacional e não-aproximabilidade. Serão investigados problemas sobre grafos, que se inserem na linha de "partição" e "empacotamento": duas linhas fundamentais e de grande interesse prático e teórico. Na primeira, os estudos tratarão de partições conexas e balanceadas; na segunda, serão considerados empacotamentos de famílias pré-fixadas de grafos. (AU) | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |