Atribuição de papéis em alguns produtos de grafos

Página do item simplificado
dc.contributor.advisor-co1Dias, Elisângela Silva
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/0138908377103572pt_BR
dc.contributor.advisor-co2Nascimento, Julliano Rosa
dc.contributor.advisor-co2Latteshttp://lattes.cnpq.br/8971175373328824pt_BR
dc.contributor.advisor1Castonguay, Diane
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/4005898623592261pt_BR
dc.contributor.referee1Castonguay, Diane
dc.contributor.referee2Rodrigues, Rosiane de Freitas
dc.contributor.referee3Dourado, Mitre Costa
dc.contributor.referee4Nobrega, Diana Sasaki
dc.contributor.referee5Silva, Hebert Coelho da
dc.creatorMesquita, Fernanda Neiva
dc.creator.Latteshttps://lattes.cnpq.br/3639678638834402pt_BR
dc.date.accessioned2022-07-18T12:59:32Z
dc.date.available2022-07-18T12:59:32Z
dc.date.issued2022-06-24
dc.description.abstractDuring the pandemic, due to the new coronavirus (COVID-19), the use of social networks was enhanced by social distancing and the need to stay connected, generating a gigantic volume of data. In order to extract information, graphs constitute a powerful modeling tool in which the vertices represent individuals and the edges represent relationships between them. In 1991, Everett and Borgatti formalized the concept of role assignment under the name role coloring. Thus, a r-role assignment of a simple graph G is an assignment of r distinct roles to the vertices of G, such that two vertices with the same role have the same set of roles in the related vertices. Furthermore, a specific r-role assignment defines a role graph, in which the vertices are the distinct r roles, and there is an edge between two roles whenever there are two related vertices in the graph G that correspond to these roles. Research on role assignment and operations on graphs is scarce. We showed a dichotomy for the r-role assignment problem for the Cartesian product. While the Cartesian product of two graphs always admits a 2-role assignment, the problem remains NP-complete for any fixed r ≥ 3. The complementary prism arises from the complementary product, introduced by Haynes, Henning and Van Der Merwe in 2019, which is a generalization of the Cartesian product. Complementary prisms admits a 2-role assignment, with the exception of the complementary prism of a path with three vertices. We verified that the complementary prisms admits a 3-role assignment, with the exception of the complementary prism of some not connected bipartite graphs. Next, we showed that the related problem can be solved in linear time. Finally, we conjecture that, for r ≥ 3 the problem of (r+1)-role assignment to complementary prisms is NP-complete. In this sense, we consider the role graph K'_{1,r} which is the bipartite graph K_{1,r} with a loop at the vertex of degree r and we highlight that the problem of deciding whether a prism complement has a (r+1)-role assignment, when the role graph is K'_{1,r}, it is NP-complete.eng
dc.description.provenanceSubmitted by Leandro Machado (leandromachado@ufg.br) on 2022-07-13T18:35:23Z No. of bitstreams: 2 Tese - Fernanda Neiva Mesquita - 2022.pdf: 2243804 bytes, checksum: 8a9f8493124f48e8541d48480839654a (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceRejected by Luciana Ferreira (lucgeral@gmail.com), reason: Pesquise se os dois co-orientadores possuem ORCID e lattes, pois não preencheu esses campos. on 2022-07-15T12:58:04Z (GMT)en
dc.description.provenanceSubmitted by Leandro Machado (leandromachado@ufg.br) on 2022-07-15T15:35:18Z No. of bitstreams: 2 Tese - Fernanda Neiva Mesquita - 2022.pdf: 2243804 bytes, checksum: 8a9f8493124f48e8541d48480839654a (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2022-07-18T12:59:32Z (GMT) No. of bitstreams: 2 Tese - Fernanda Neiva Mesquita - 2022.pdf: 2243804 bytes, checksum: 8a9f8493124f48e8541d48480839654a (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceMade available in DSpace on 2022-07-18T12:59:32Z (GMT). No. of bitstreams: 2 Tese - Fernanda Neiva Mesquita - 2022.pdf: 2243804 bytes, checksum: 8a9f8493124f48e8541d48480839654a (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5) Previous issue date: 2022-06-24en
dc.description.resumoDurante a pandemia, devido ao novo coronavírus (COVID-19), o uso das redes sociais foi po- tencializado pelo distanciamento social e a necessidade de se manter conectados, gerando um volume gigantesco de dados. A fim de extrair informações, os grafos constituem uma ferramenta de modelagem poderosa em que os vértices representam indivíduos e as arestas relações entre eles. Em 1991, Everett e Borgatti formalizaram o conceito de atribuição de papéis sob o nome de role coloring. Assim, uma r-atribuição de papéis de um grafo simples G é uma atribuição de r papéis distintos aos vértices de G, tal que, dois vértices com o mesmo papel têm o mesmo conjunto de papéis nos vértices relacionados. Além disso, uma r-atribuição de papéis específica define um grafo de papéis, no qual os vértices são os r papéis distintos, e existe uma aresta entre dois papéis sempre que há dois vértices relacionados no grafo G que correspondem a esses papéis. Pesquisas sobre atribuição de papéis e operações em grafos são escassas. Mostramos uma dicotomia para o problema de r-atribuição de papéis para o produto Cartesiano. Enquanto, o produto Cartesiano de dois grafos sempre admite uma 2- atribuição de papéis, o problema permanece NP-completo para qualquer r ≥ 3 fixo. O prisma complementar surge do produto complementar, introduzido por Haynes, Henning e Van Der Merwe em 2019, que é uma generalização do produto Cartesiano. Os prismas complementares admitem uma 2-atribuição de papéis, com exceção do prisma complementar de um caminho com três vértices. Verificamos que os prismas complementares admitem uma 3- atribuição de papéis, com exceção do prisma complementar de alguns grafos bipartidos. Em seguida, mostramos que o problema relacionado pode ser resolvido em tempo linear. Por último, conjeturamos que, para r ≥ 3, o problema de (r+1)-atribuição de papéis para prismas complementares é NP-completo. Neste sentido, consideramos o grafo de papéis K'_{1,r} que é o grafo bipartido K_{1,r} com laço no vértice de grau r e destacamos que o problema de decidir se um prisma complementar tem uma (r+1)-atribuição de papéis, quando o grafo de papéis é K'_{1,r}, é NP-completo.pt_BR
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpt_BR
dc.description.sponsorshipFundação de Amparo à Pesquisa do Estado de Goiáspt_BR
dc.identifier.citationMESQUITA, F. N. Atribuição de papéis em alguns produtos de grafos. 2022. 130 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2022.pt_BR
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/12185
dc.languageporpt_BR
dc.publisherUniversidade Federal de Goiáspt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto de Informática - INF (RG)pt_BR
dc.publisher.initialsUFGpt_BR
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)pt_BR
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 International*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectAtribuição de papéispor
dc.subjectProduto cartesianopor
dc.subjectPrisma complementarpor
dc.subjectRedes sociaispor
dc.subjectRole assignmenteng
dc.subjectCartesian producteng
dc.subjectComplementary prismeng
dc.subjectSocial networkseng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAOpt_BR
dc.titleAtribuição de papéis em alguns produtos de grafospt_BR
dc.title.alternativeRole assignments in some product of grapheng
dc.typeTesept_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Tese - Fernanda Neiva Mesquita - 2022.pdf
Tamanho:
2.14 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação