Doutorado em Ciência da Computação
URI Permanente para esta coleção
Navegar
Navegando Doutorado em Ciência da Computação por Por Orientador "Castonguay, Diane"
Agora exibindo 1 - 2 de 2
Resultados por página
Opções de Ordenação
Item Atribuição de papéis em alguns produtos de grafos(Universidade Federal de Goiás, 2022-06-24) Mesquita, Fernanda Neiva; Dias, Elisângela Silva; http://lattes.cnpq.br/0138908377103572; Nascimento, Julliano Rosa; http://lattes.cnpq.br/8971175373328824; Castonguay, Diane; http://lattes.cnpq.br/4005898623592261; Castonguay, Diane; Rodrigues, Rosiane de Freitas; Dourado, Mitre Costa; Nobrega, Diana Sasaki; Silva, Hebert Coelho daDuring 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.Item Problema de particionamento em subgrafos complementares: complexidade e convexidade(Universidade Federal de Goiás, 2019-11-11) Nascimento, Julliano Rosa; Coelho, Erika Morais Martins; http://lattes.cnpq.br/9389487015938509; Castonguay, Diane; http://lattes.cnpq.br/4005898623592261; Castonguay, Diane; Coelho, Erika Morais Martins; Protti, Fábio; Szwarcfiter, Jayme Luiz; Pinto, Leizer de LimaIn this work, we introduce the PARTITION INTO COMPLEMENTARY SUBGRAPHS (COMP-SUB(Pi)) problem, which receives as input a graph H and an edge set property Pi, and the goal is determining whether is possible to decompose the graph H into complementary subgraphs G and \bar{G} such that the edge set M between G and \bar{G} satisfies property Pi. COMP-SUB(Pi) generalizes the recognition of complementary prisms problem, which is the case when Pi is a perfect matching between corresponding vertices of G and \bar{G}. When Pi is arbitrary, we show results for k-clique or k-independent set free graphs. On property P_\emptyset which considers M =\emptyset, we show that COMP-SUB(P_\emptyset) is GI-complete for chordal graphs, but can be solved efficiently for permutation, comparability, co- comparability and co-interval graphs. Furthermore, we obtain characterizations for some subclasses of chordal graphs. We also obtain results for Pi_{Kn,n} , the case when M has all the possible edges between G and \bar{G} and for Pi_{PERF}, the case which considers M as a perfect matching. In particular, we show that COMP-SUB(Pi_{PERF}) problem is GI-hard, and we obtain characterizations for this problem when the input graph H is a cograph, a chordal or a distance-hereditary graph. On the other hand, we address three parameters of the geodetic convexity for complementary prisms: the hull number, the geodetic number and the convexity number. We obtain results on the hull number for complementary prisms G\bar{G} when both G e \bar{G} are connected. On the second and third parameter, we show that the decision problems related to the geodetic number and convexity number are NP-complete even restricted to complementary prisms. We also establish lower bounds on the geodetic number for G\bar{G} when G or \bar{G} have simplicial vertices and we determine the convexity number for G\bar{G} when G is disconnected, or G is a cograph.