Algoritimos de aproximacao, complexidade e nao-aproximabilidade de problemas em grafos.

• 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)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

CHATAIGNER, F.; MANIC, G.; WAKABAYASHI, Y.; YUSTER, R.. Approximation algorithms and hardness results for the clique packing problem. DISCRETE APPLIED MATHEMATICS, v. 157, n. 7, p. 1396-1406, APR 6 2009. (05/53840-0, 06/01817-7, 03/09925-5)