Correspondência inexata entre grafos (2008)
- Autores:
- Autor USP: FREIRE, ALEXANDRE DA SILVA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Idioma: Português
- Resumo: Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial.Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema
- Imprenta:
- Data da defesa: 02.07.2008
-
ABNT
FREIRE, Alexandre da Silva. Correspondência inexata entre grafos. 2008. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2008. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/. Acesso em: 16 abr. 2024. -
APA
Freire, A. da S. (2008). Correspondência inexata entre grafos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/ -
NLM
Freire A da S. Correspondência inexata entre grafos [Internet]. 2008 ;[citado 2024 abr. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/ -
Vancouver
Freire A da S. Correspondência inexata entre grafos [Internet]. 2008 ;[citado 2024 abr. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/ - Empacotamento de bicliques em grafos bipartidos
- A branch-and-bound algorithm for the maximum capture problem with random utilities
- Minimum ratio cover of matrix columns by extreme rays of its induced cone
- Método exato para um problema de alocação justa
- A column generation approach for the graph matching problem
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
