Busca avançada
Ano de início
Entree

Otimização discreta e grafos: algoritmos, teoria e aplicações

Processo: 08/06508-8
Modalidade de apoio:Auxílio à Pesquisa - Jovens Pesquisadores
Vigência: 01 de dezembro de 2008 - 30 de novembro de 2011
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Gordana Manic
Beneficiário:Gordana Manic
Instituição Sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil
Assunto(s):Matemática discreta  Teoria dos grafos  Algoritmos de aproximação  Combinatória poliédrica  Análise de algoritmos 
Palavra(s)-Chave do Pesquisador:Algoritmos de Aproximação | Análise de Algoritmos e Complexidade de Computação | Combinatória Poliédrica | teoria dos grafos | Matemática Discreta e Combinatória
Publicação FAPESP:https://media.fapesp.br/bv/uploads/pdfs/Investindo...pesquisadores_217_173_174.pdf

Resumo

O foco central da proposta é a investigação de problemas de otimização discreta e grafos, com ênfase em seus aspectos teóricos, algorítmicos e aplicados. Dentre os problemas de otimização discreta que investigaremos incluem-se: Intercalação Ótima de Datapath em Sistemas Reconfiguráveis e o Problema do Máximo Subgrafo Comum. O projeto será concentrado no estudo de técnicas para a solução destes problemas, implementação eficiente dessas técnicas para a solução de problemas reais. Já na área de grafos e combinatória, as pesquisas terão caráter mais teórico. Na área de grafos, serão pesquisados problemas de Empacotamento de Subgrafos em Grafos, entre outros. Desejamos responder à questão da existência ou não de algoritmos com garantia de aproximação melhor do que as já conhecidas; para certas classes especiais de grafos, exibir algoritmos polinomiais, ou melhorar razões de aproximação conhecidas e provar limitantes de aproximação. (AU)

Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações científicas (4)
(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)
BAHIENSE, LAURA; MANIC, GORDANA; PIVA, BRENO; DE SOUZA, CID C.. The maximum common edge subgraph problem: A polyhedral investigation. DISCRETE APPLIED MATHEMATICS, v. 160, n. 18, p. 19-pg., . (08/06508-8)
MANIC, GORDANA; MARTIN, DANIEL M.; STOJAKOVIC, MILOS. On Bichromatic Triangle Game. DISCRETE APPLIED MATHEMATICS, v. 164, n. 2, SI, p. 400-405, . (08/06508-8)
BAHIENSE, LAURA; MANIC, GORDANA; PIVA, BRENO; DE SOUZA, CID C.. The maximum common edge subgraph problem: A polyhedral investigation. DISCRETE APPLIED MATHEMATICS, v. 160, n. 18, SI, p. 2523-2541, . (08/06508-8)
MANIC, GORDANA; MARTIN, DANIEL M.; STOJAKOVIC, MILOS. On Bichromatic Triangle Game. DISCRETE APPLIED MATHEMATICS, v. 164, p. 6-pg., . (08/06508-8)

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.