| Processo: | 06/01817-7 |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Vigência (Início): | 01 de setembro de 2006 |
| Vigência (Término): | 14 de fevereiro de 2008 |
| Área do conhecimento: | Ciências Exatas e da Terra - Ciência da Computação |
| Pesquisador responsável: | Cid Carvalho de Souza |
| Beneficiário: | Gordana Manic |
| Instituição Sede: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil |
| Assunto(s): | Otimização combinatória Combinatória poliédrica Programação linear inteira Branch-and-cut Algoritmos |
| Palavra(s)-Chave do Pesquisador: | Algoritmos De Branch-And-Cut | Combinatoria Poliedrica | Isomorfismo Em Grafos | Otimizacao Combinatoria | Programacao Linear Inteira | Otimização Combinatória |
Resumo O objetivo deste projeto é estudar problemas de OtimizaçãoCombinatória relacionados ao isomorfismo de subgrafos e algumas desuas aplicações práticas. Em particular, estamos interessados eminvestigar os problemas do "Máximo Subgrafo Comum" (MCS) e de"Intercalação Ótima de Datapath em Sistemas Reconfiguráveis" (DPM). NoMCS deve-se encontrar o maior subgrafo comum a uma coleção de grafos,considerando-se os atributos dos vértices e a topologia dos grafos.Dentre as aplicações deste problema podemos citar o reconhecimento depadrões em imagens, visão computacional, video indexing, além da buscapor similaridades em estruturas moleculares, que são de grandeinteresse em Química e Biologia. Por outro lado, a computaçãoreconfigurável propiciou a criação de arquiteturas alternativas para oprojeto de sistemas digitais complexos, permitindo aos projetistasconciliar a flexibilidade do software com o desempenho do hardware.Neste contexto, surge o DPM que consiste em combinar trechos daaplicação representados como grafos de fluxo de dados e controle paraencontrar um datapath reconfigurável equivalente com área mínima. Apesquisa proposta aqui está focada em investigações teóricas sobrea estrutura facial dos politopos dos problemas MCS e DPM, e nodesenvolvimento de algoritmos exatos utilizando Programação LinearInteira. Espera-se que os resultados alcançados sirvam para aresolução de instâncias de tamanho equivalente àquelas oriundas deaplicações reais. (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) | |