Algoritmo prático para p-partição da convexidade p3 em grafos com treewidth limitada

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOliveira, Rodolfo Alves de-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9144709891245526-
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5898801580033554-
Autor(es): dc.contributorBêdo, Marcos Vinícius Naves-
Autor(es): dc.contributorhttp://lattes.cnpq.br/8199158119583569-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9469952297613499-
Autor(es): dc.creatorCastro, Lorrana Filemes de-
Data de aceite: dc.date.accessioned2024-07-11T17:41:11Z-
Data de disponibilização: dc.date.available2024-07-11T17:41:11Z-
Data de envio: dc.date.issued2023-06-05-
Data de envio: dc.date.issued2023-06-05-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/29062-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/755379-
Descrição: dc.descriptionNeste trabalho, abordamos o problema da p-partição na convexidade P3 em grafos com treewidth limitado. Dados um grafo G = (V,E) e S ⊆V, dizemos que S é um conjunto p3-convexo se todo vértice com pelo menos dois vizinhos em S a ele pertence. Assim, o problema da ppartição na convexidade P3 nos desafia a encontrar, se possível, um particionamento para V em p conjuntos p3-convexos não vazios e mutualmente disjuntos, onde p ≥ 2 é um inteiro. Apesar da conhecida NP-completude mesmo para grafos split, mostramos em detalhes um algoritmo que resolve o problema da p-partição em tempo linear quando a treewidth de G e um número p limitado são ambos constantes.-
Descrição: dc.descriptionIn this work we tackle the p-partitioning problem for P3-convexity in graphs with limited treewidth. Given a graph G = (V,E) and S ⊆ V, S is a p3-convex set whenever every vertex with at least two neighbors in S also belongs to S. Consequently, for any integer p ≥ 2, the ppartitioning problem in P3-convexity challenges us to find a partition of V into nonempty and mutually disjoint p3-convex sets. Despite the NP-completeness even for split graphs, we show an algorithm that solves the p-partitioning problem in linear time for limited a constraint values of the treewidth and p.-
Descrição: dc.description37 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectGrafos-
Palavras-chave: dc.subjectÁrvore de Decomposição-
Palavras-chave: dc.subjectTreewidth-
Palavras-chave: dc.subjectConvexidade P3-
Palavras-chave: dc.subjectGraph-
Palavras-chave: dc.subjectDecomposition Tree-
Palavras-chave: dc.subjectTreewidth-
Palavras-chave: dc.subjectP3-Convexity-
Título: dc.titleAlgoritmo prático para p-partição da convexidade p3 em grafos com treewidth limitada-
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.