Tese de Doutorado
DOI
https://doi.org/10.11606/T.45.2006.tde-20210729-150559
Documento
Autor
Nome completo
Gordana Manic
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2006
Orientador
Título em português
Empacotamento de subgrafos em grafos
Palavras-chave em português
Teoria Dos Grafos
Resumo em português
Dentre os problemas clássicos da área de otimização combinatória distinguem-se os chamados problemas de empacotamento, que variam de acordo com os objetos a serem empacotados e as funções a serem otimizadas. Quando os onjetos de interesse são grafos, vários desses problemas podem ser classificados como problemas de F-empacotamento, onde F é uma família de grafos.Estes problemas são assim definidos: dado um grafo G, encontrar em G um subgrafo H que seja uma união de grafos disjuntos nos vértices (ou nas arestas), cada um dos quais é isomorfo a algum grafo da família F, e tal que H tenha o maior número possível de vértices (ou arestas). Temos assim várias variantes, dependendo se considerarmos disjunção nos vértices ou nas arestas, e se queremos maximizar o número de vértices ou arestas de H.
Título em inglês
not available
Resumo em inglês
not available
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2021-07-29