Busca avançada
Ano de início
Entree

Modelagem matemática e aplicações de problemas de otimização relativos a busca de subgrafos com estruturas comuns

Processo: 06/01817-7
Linha de fomento: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

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)

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. Citações Web of Science: 4.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.