Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Nogueira, Loana | - |
Autor(es): dc.contributor | Protti, Fábio | - |
Autor(es): dc.contributor | Cunha, Luís Felipe Ignácio | - |
Autor(es): dc.contributor | Bravo, Raquel | - |
Autor(es): dc.creator | Carneiro, Hugo Caetano Borges | - |
Data de aceite: dc.date.accessioned | 2024-07-11T17:27:51Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T17:27:51Z | - |
Data de envio: dc.date.issued | 2021-07-28 | - |
Data de envio: dc.date.issued | 2021-07-28 | - |
Data de envio: dc.date.issued | 2020 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/22758 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/750817 | - |
Descrição: dc.description | Nesse 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.description | In 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | http://creativecommons.org/licenses/by-nc-nd/3.0/br/ | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | P4-esparso | - |
Palavras-chave: dc.subject | Grafos − 2F | - |
Palavras-chave: dc.subject | Arboricidade | - |
Palavras-chave: dc.subject | Floresta | - |
Palavras-chave: dc.subject | Ciência da computação | - |
Palavras-chave: dc.subject | Teoria dos grafos | - |
Palavras-chave: dc.subject | Floresta | - |
Palavras-chave: dc.subject | P4-sparse graph | - |
Palavras-chave: dc.subject | 2F-graph | - |
Palavras-chave: dc.subject | Arboricity | - |
Palavras-chave: dc.subject | Forest | - |
Título: dc.title | Partição de grafos perfeitos em duas florestas | - |
Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: