Sobre fatores e empacotamentos em grafos (1997)
- Autores:
- Autor USP: RODRIGUES, ESTELA MARIS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: TEORIA DOS GRAFOS
- Idioma: Português
- Resumo: 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
-
ABNT
RODRIGUES, Estela Maris. Sobre fatores e empacotamentos em grafos. 1997. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1997. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013855/. Acesso em: 23 abr. 2024. -
APA
Rodrigues, E. M. (1997). Sobre fatores e empacotamentos em grafos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013855/ -
NLM
Rodrigues EM. Sobre fatores e empacotamentos em grafos [Internet]. 1997 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013855/ -
Vancouver
Rodrigues EM. Sobre fatores e empacotamentos em grafos [Internet]. 1997 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013855/
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
