INF - Instituto de Informática

URI Permanente desta comunidade

http://200.137.215.59/tede/handle/tde/145

Navegar

Navegando INF - Instituto de Informática por Por Orientador "Castonguay, Diane"

Agora exibindo 1 - 4 de 4
  • Nenhuma Miniatura disponível
    Item
    Definitividade de formas quadráticas – uma abordagem polinomial
    (Universidade Federal de Goiás, 2016-11-18) Alves, Jesmmer da Silveira; Brustle, Thomas; http://www2.ubishops.ca/algebra/brustleCv.pdf; Castonguay, Diane; http://lattes.cnpq.br/4005898623592261; Castonguay, Diane; http://lattes.cnpq.br/4005898623592261; Centeno, Carmen; Alvares, Edson Ribeiro; Martinez, Fabio Henrique Viduani; Longo, Humberto José
    Quadratic forms are algebraic expressions that have important role in different areas of computer science, mathematics, physics, statistics and others. We deal with rational quadratic forms and integral quadratic forms, with rational and integer coefficients respectively. Existing methods for recognition of rational quadratic forms have exponential time complexity or use approximation that weaken the result reliability. We develop a polinomial algorithm that improves the best-case of rational quadratic forms recognition in constant time. In addition, new strategies were used to guarantee the results reliability, by representing rational numbers as a fraction of integers, and to identify linear combinations that are linearly independent, using Gauss reduction. About the recognition of integral quadratic forms, we identified that the existing algorithms have exponential time complexity for weakly nonnegative type and are polynomial for weakly positive type, however the degree of the polynomial depends on the algebra dimension and can be very large. We have introduced a polynomial algorithm for the recognition of weakly nonnegative quadratic forms. The related algorithm identify hypercritical restrictions testing every subgraph of 9 vertices of the quadratic form associated graph. By adding Depth First Search approach, a similar strategy was used in the recognition of weakly positive type. We have also shown that the recognition of integral quadratic forms can be done by mutations in the related exchange matrix.
  • Imagem de Miniatura
    Item
    Reconhecimento polinomial de álgebras cluster de tipo finito
    (Universidade Federal de Goiás, 2015-09-09) Dias, Elisângela SIlva; Castonguay, Diane; http://lattes.cnpq.br/4005898623592261; Castonguay, Diane; Schiffler, Ralf; Dourado, Mitre Costa; Carvalho, Marcelo Henrique de; Longo, Humberto José
    Cluster algebras form a class of commutative algebra, introduced at the beginning of the millennium by Fomin and Zelevinsky. They are defined constructively from a set of generating variables (cluster variables) grouped into overlapping subsets (clusters) of fixed cardinality. Since its inception, the theory of cluster algebras found applications in many areas of science, specially in mathematics. In this thesis, we study, with computational focus, the recognition of cluster algebras of finite type. In 2006, Barot, Geiss and Zelevinsky showed that a cluster algebra is of finite type whether the associated graph is cyclically oriented, i.e., all chordless cycles of the graph are cyclically oriented, and whether the skew-symmetrizable matrix associated has a positive quasi-Cartan companion. At first, we studied the two topics independently. Related to the first part of the criteria, we developed an algorithm that lists all chordless cycles (polynomial on the length of those cycles) and another that checks whether a graph is cyclically oriented and, if so, list all their chordless cycles (polynomial on the number of vertices). Related to the second part of the criteria, we developed some theoretical results and we also developed a polynomial algorithm that checks whether a quasi-Cartan companion matrix is positive. The latter algorithm is used to prove that the problem of deciding whether a skew-symmetrizable matrix has a positive quasi-Cartan companion for general graphs is in NP class. We conjecture that this problem is in NP-complete class.We show that the same problem belongs to the class of polynomial problems for cyclically oriented graphs and, finally, we show that deciding whether a cluster algebra is of finite type also belongs to this class.
  • Nenhuma Miniatura disponível
    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 da
    During 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.
  • Nenhuma Miniatura disponível
    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 Lima
    In 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.