Correspondência inexata entre grafos (2008)
- Authors:
- Autor USP: FREIRE, ALEXANDRE DA SILVA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2008.tde-16092008-133830
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Language: Português
- Abstract: 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
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
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: https://teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/. Acesso em: 06 maio 2026. -
APA
Freire, A. da S. (2008). Correspondência inexata entre grafos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/ -
NLM
Freire A da S. Correspondência inexata entre grafos [Internet]. 2008 ;[citado 2026 maio 06 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/ -
Vancouver
Freire A da S. Correspondência inexata entre grafos [Internet]. 2008 ;[citado 2026 maio 06 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/ - A branch-and-bound algorithm for the maximum capture problem with random utilities
- Empacotamento de bicliques em grafos bipartidos
- 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
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
