Exportar registro bibliográfico

Correspondência inexata entre grafos (2008)

  • Authors:
  • Autor USP: FREIRE, ALEXANDRE DA SILVA - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • 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
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      FREIRE, Alexandre da Silva; FERREIRA, Carlos Eduardo. Correspondência inexata entre grafos. 2008.Universidade de São Paulo, São Paulo, 2008. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/ >.
    • APA

      Freire, A. da S., & Ferreira, C. E. (2008). Correspondência inexata entre grafos. 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, Ferreira CE. Correspondência inexata entre grafos [Internet]. 2008 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/
    • Vancouver

      Freire A da S, Ferreira CE. Correspondência inexata entre grafos [Internet]. 2008 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-16092008-133830/


Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020