• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.1997.tde-20210729-013855
Documento
Autor
Nombre completo
Estela Maris Rodrigues
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 1997
Director
Título en portugués
Sobre fatores e empacotamentos em grafos
Palabras clave en portugués
Teoria Dos Grafos
Resumen en portugués
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 em termos 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
Título en inglés
not available
Resumen en inglés
not available
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-07-29
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.