Sobre fatores e empacotamentos em grafos (1997)
- Authors:
- Autor USP: RODRIGUES, ESTELA MARIS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.1997.tde-20210729-013855
- Assunto: 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
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
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: 15 abr. 2026. -
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 2026 abr. 15 ] 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 2026 abr. 15 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-013855/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
