Exportar registro bibliográfico

Homeomorfismo em grafos: algoritmos e complexidade computacional (1993)

  • Authors:
  • USP affiliated authors: BENATTI, HAROLDO GONÇALVES - IME
  • Unidades: IME
  • Sigla do Departamento: MAC
  • Subjects: TEORIA DOS GRAFOS
  • Language: Português
  • Abstract: Neste trabalho estudamos varios problemas que envolvem homeomorfismo de grafos procurando responder questoes referentes a sua complexidade computacional e a existencia de algoritmos polinomiais para resolve-los. Estudamos relacoes entre aresta-homeomorfismo e vertice-homeomorfismo. Algumas destas relacoes sao utilizadas para provar a np-completude de varios problemas de homeoformismo sem padraofixo. No caso orientado, para os problemas com padrao fixo sao conhecidos algoritmos polinomiais, para apenas alguns padroes. Ja no caso nao orientado, existe um algoritmo polinoamial que resolve o problema de qualquer padrao, mas este algoritmo nao e suscetivel a uma implementacao eficiente. Isto motivou o estudo destes problemas com entradas restritas a classes particulares de grafos. Apresentamos algoritmos polinomiais, em alguns casos bem eficientes, para a classe dos grafosplanares. Por ultimo estudamos a complexidade de alguns problemas de modularidade de caminhos e circuitos em grafos orientados. Estes resultados foram obtidos usando problemas de homeomorfismo com padrao fixo. Analisamos a complexidade desses mesmos problemas quando restritos a classe dos grafos bipartidos e constatamos que esta restricao, em geral, nao altera a complexidade destes problemas
  • Imprenta:
  • Data da defesa: 29.10.1993

  • How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      BENATTI, Haroldo Goncalves; WAKABAYASHI, Yoshiko. Homeomorfismo em grafos: algoritmos e complexidade computacional. 1993.Universidade de São Paulo, São Paulo, 1993.
    • APA

      Benatti, H. G., & Wakabayashi, Y. (1993). Homeomorfismo em grafos: algoritmos e complexidade computacional. Universidade de São Paulo, São Paulo.
    • NLM

      Benatti HG, Wakabayashi Y. Homeomorfismo em grafos: algoritmos e complexidade computacional. 1993 ;
    • Vancouver

      Benatti HG, Wakabayashi Y. Homeomorfismo em grafos: algoritmos e complexidade computacional. 1993 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

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