Partição de grafos perfeitos em duas florestas

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorNogueira, Loana-
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorCunha, Luís Felipe Ignácio-
Autor(es): dc.contributorBravo, Raquel-
Autor(es): dc.creatorCarneiro, Hugo Caetano Borges-
Data de aceite: dc.date.accessioned2024-07-11T17:27:51Z-
Data de disponibilização: dc.date.available2024-07-11T17:27:51Z-
Data de envio: dc.date.issued2021-07-28-
Data de envio: dc.date.issued2021-07-28-
Data de envio: dc.date.issued2020-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/22758-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/750817-
Descrição: dc.descriptionNesse trabalho consideramos um problema bastante estudado na teoria dos grafos: o problema do particionamento em grafos. Nosso objetivo consiste em, dado um grafo P4-esparso qualquer, verificar se seu conjunto de vértices pode ser particionado em duas florestas induzidas, ou seja, dois grafos acíclicos. Grafos cujo conjunto de vértices pode ser particionado em duas florestas são chamados grafos-2F. Nosso resultado consiste em apresentar uma caracterização por subgrafos minimais proibidos para a classe dos grafos P4 −esparsos 2F. Em outras palavras, apresentamos uma família F de subgrafos tal que se um grafo P4-esparso G não contém nenhum desses grafos como subgrafo induzido então G ´e 2F. Para o caso da arboricidade p, generalizamos nossa família de subgrafos proibidos e observamos que cada grafo nessa família é uma obstrução, mininal para arboricidade p. No entanto, uma vez que o número de obstruções minimais P4-esparsas para arboricidade p cresce exponencialmente, não é um possível uma caracterização análoga aquela para arboricidade 2-
Descrição: dc.descriptionIn this work we consider the problem of partitioning a given set belonging to a P4-sparse graph into two induced forests (i.e., an acyclic graph). Those graphs whose set of vertices can be partitioned into two forest will be called 2F. We provide a characterization of such graphs by minimal forbidden patterns and a polynomial time algorithm to recognize them. Or equivalently, we present a family F of graphs such that if a P4-sparse graph G does not contain any graph from F as an induced subgraph, then G is a 2F − graph. For the problem of arboricity p in P4-sparse graphs, we generalize our family of forbidden subgraphs and show that each graph in this family is an minimal obstruction of arboricity p. However, there is no analogue to our main result since the number of P4-sparse minimal obstructions for arboricity p grows exponencially with p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/br/-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectP4-esparso-
Palavras-chave: dc.subjectGrafos − 2F-
Palavras-chave: dc.subjectArboricidade-
Palavras-chave: dc.subjectFloresta-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectFloresta-
Palavras-chave: dc.subjectP4-sparse graph-
Palavras-chave: dc.subject2F-graph-
Palavras-chave: dc.subjectArboricity-
Palavras-chave: dc.subjectForest-
Título: dc.titlePartição de grafos perfeitos em duas florestas-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.