Ver registro no DEDALUS
Exportar registro bibliográfico

Sobre fatores e empacotamentos em grafos (1997)

  • Authors:
  • USP affiliated authors: RODRIGUES, ESTELA MARIS - IME
  • USP Schools: IME
  • Sigla do Departamento: MAC
  • Subjects: TEORIA DOS GRAFOS
  • Language: Português
  • Abstract: Uma generalização de emparelhamentos em grafos pode ser obtida com base na idéia de encontrarmos, em um garfo H = (V(H),A(H)), um subgrafo G tal que os componentes de G sejam isomorfos a membros de uma família fixa F de grafos conexos. Ao grafo G chamamos F-empracotamento de H, e se V (G) = V(H), então G é denominado um F-fator de H. Um de nossos objetivos é o estudo da complexidade dos problemas da forma "dado um grafo H, decidir se H admite um F-fator". Chamamos este problema de problema de fatoração definido por F. Os problemas de fatoração definidos por famílias unitárias foram os primeiros a serem estudados. Dentre esses, o problema do emparelhamento perfeito é o único, em essência, que não é NP-completo. Dentre os problemas definidos por famílias não unitárias, são conhecidas algumas classes de problemas polinomiais. Exemplos são os problemas de fatoração por famílias de cliques que contenham o grafo 'K IND.2', e alguns problemas definidos por familias de estrelas. Todos esses problemas são considerados neste trabalho. Também apresentamos exemplos de problemas NP-completos definidos por famílias não unitárias de grafos, por exemplo o problema do {'K IND.3', 'K IND.4',...}-fator e alguns problemas definidos por famílias de grafos bipartidos completos. Atualmente, a maior questão acerca dos problemas de fatoração é a conjectura de Loebl e Poljak, que propõe uma caracterização das famílias de grafos conexos que definem problemas de fatoração polinomiais emtermos de matróides. Essa conjectura foi respondida de forma afirmativa para famílias da forma {'K IND.2', F} em que F é um grafo conexo. O caso geral permanece em aberto desde que foi proposto em 1988
  • Imprenta:
  • Data da defesa: 24.02.1997

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

    • ABNT

      RODRIGUES, Estela Maris; GURGEL, Maria Angela Melo de Campos. Sobre fatores e empacotamentos em grafos. 1997.Universidade de São Paulo, São Paulo, 1997.
    • APA

      Rodrigues, E. M., & Gurgel, M. A. M. de C. (1997). Sobre fatores e empacotamentos em grafos. Universidade de São Paulo, São Paulo.
    • NLM

      Rodrigues EM, Gurgel MAM de C. Sobre fatores e empacotamentos em grafos. 1997 ;
    • Vancouver

      Rodrigues EM, Gurgel MAM de C. Sobre fatores e empacotamentos em grafos. 1997 ;

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