http://www.bdtd.uerj.br/handle/1/21507 Mon, 20 Apr 2026 22:24:42 GMT 2026-04-20T22:24:42Z http://www.bdtd.uerj.br/handle/1/25546 Título: Representações Monte Carlo, Las Vegas e Determinística de Grafos Massivos Autor: Leão, Paulo Diogo Rodrigues Primeiro orientador: Oliveira, Fabiano de Souza Abstract: Lossless compact and probabilistic graph representations aim to reduce the space occupied by classical representations, such as the adjacency list and edge list, without compromising the accuracy of adjacency tests. In the literature, there are several techniques for compact graph representation. However, many of these approaches are limited to modifying vertex labels in order to produce more compact classical representations, or to representing more restricted classes of graphs. Few proposals exist for modeling general graphs with an emphasis on compactness of representation. This thesis investigates a recent variant of the XOR filter, called Spatial XOR, which introduces the concept of contiguous windows in the mapping vector of hash functions. We developed an empirical and computational methodology to estimate the optimal size of these windows and the maximum load factor, employing machine learning techniques (leave-one-out validation) and large-scale empirical analysis. Additionally, two new lossless graph representations are proposed. The first is based on the use of hash functions, combining explicit and implicit neighborhood lists, resulting in a Las Vegas–type randomized data structure; the second employs modular arithmetic to represent neighborhoods through systems of congruences. The experiments demonstrated that the probabilistic representation achieves greater compactness, while the modular representation provides a significantly shorter construction time, maintaining space efficiency compared to traditional adjacency lists. Instituição: Universidade do Estado do Rio de Janeiro Tipo do documento: Tese Fri, 05 Dec 2025 00:00:00 GMT http://www.bdtd.uerj.br/handle/1/25546 2025-12-05T00:00:00Z http://www.bdtd.uerj.br/handle/1/25540 Título: Sobre coloração total equilibrada de grafos snarks Autor: Souza, Rieli Araújo Primeiro orientador: Nóbrega, Diana Sasaki Abstract: A total coloring of a graph G is an assignment of k colors to the elements of G, where the elements are the vertices and the edges. When such coloring does not allow that adjacent or incident elements to share the same color, it is denoted as a proper total coloring. The total chromatic number of graph G is the smallest value of k necessary to obtain a proper total coloring, it is denoted by χ′′(G). In 1994, Hung-Lin Fu introduced the concept of equitable total coloring, such that the difference between the cardinalities of any two colors is at most 1. The equitable total chromatic number of a graph G is the smallest value of k necessary to obtain an equitable total coloring, it is denoted by χ′′ e (G). Fu conjectured that for a simple graph, the χ′′ e (G) is between (Δ + 1) and (Δ + 2), so that Δ is the maximum degree of graph. Although the conjecture remains open, in 2002, Wei-Fan Wang demonstrated its validity for cubic graphs, showing that the equitable total chromatic number is between 4 and 5. The focus of this work is a special class of cubic graphs that have a peculiar structure, known as snarks. Snarks are cubic graphs that are cyclically 4-edge-connected, Class 2 and with a girth at least 5. In a study by Dantas el al. in 2016, a question was proposed about the existence of a cubic graph with χ′′(G) = 4, but with χ′′ e (G) = 5, and having girth at least 5. In this work, we investigate the equitable total coloring at the snarks graphs, and we obtained a 4-equitable total coloring for well-done two snarks and of all members of an infinite family: the Zamfirescu 36 and the Double Star; and the members of the second infinite family of Loupekine snarks. Instituição: Universidade do Estado do Rio de Janeiro Tipo do documento: Dissertação Mon, 23 Sep 2024 00:00:00 GMT http://www.bdtd.uerj.br/handle/1/25540 2024-09-23T00:00:00Z http://www.bdtd.uerj.br/handle/1/25175 Título: Coloração total e problema Firefighter em grafos cúbicos Autor: Orfei, Sérgio Fusquino Primeiro orientador: Nobrega, Diana Sasaki Nobrega Abstract: In this master’s thesis we tackle two problems in Graph Theory well inserted historical contexts, with open problems and with our results. We first study total coloring in graphs. A total coloring of a graph G is an assignment of colors to the edges and vertices of G so that adjacent and incident elements have different colors. Open for more than 50 years, we have the Total Coloring Conjecture as principal motivation, which limits the total chromatic number of G to its maximum degree plus two units. In this work we present the study we have developed on the total coloring of generalized Petersen graphs, classifying some infinite families of this class of graphs as Type1, exhibiting a Δ +1-total coloring for them. The main technique used to coloring them is the joining of blocks of these graphs developed y Sasaki, thus contemplating infinite graphs as we join these blocks. Another problem addressed in this work is the Firefighter problem, also approached as a combinatorial game, which consists of a scenario where a vertex is set on fire, and then, one or more vertices are chosen to be defended per step, preventing the fire from reaching these vertices or passing through them. In the subsequent steps, the fire spreads to adjacent vertices, and then another vertex to be defended is chosen. The main objectives of this problem are to defend a considerable number of vertices or to stop the fire from spreading as soon as possible. In this work, we present a lower and upper bound for the surviving rate, a parameter used to calculate the proportion of saved vertices in the graph, of three infinite families of fullerene graphs: the full icosahedral symmetry fullerene graphs Gi,0 and Gi,i and the fullerene nanodiscs Dr. Furthermore, for this approach, we propose a spiral planar representation for the full icosahedral symmetry fullerene graphs, based on the Spiral Conjecture. We also study this problem on the dual graphs of these fullerenes and on the two families of Loupekine’s snarks, LO¹k and LO²k. A part of the results in the Firefighter problem was achieved with computational assistance, and thus, we dedicate a section to present it. Instituição: Universidade do Estado do Rio de Janeiro Tipo do documento: Dissertação Tue, 19 Dec 2023 00:00:00 GMT http://www.bdtd.uerj.br/handle/1/25175 2023-12-19T00:00:00Z http://www.bdtd.uerj.br/handle/1/24755 Título: Índice Relativo de Capacidade Intrínseca: uma nova abordagem fundamentada em Ciência de Dados e inspirada no Índice de Integridade Biótica Autor: Hora, Marina Fajardo Villela Martins Pompílio da Primeiro orientador: Leite, Karla Tereza Figueiredo Abstract: Intrinsic Capacity (IC) has been widely studied; however, there are still disagree- ments regarding the construction of an indicator that fairly represents aspects of human health across the various socioeconomic contexts observed in patients around the world. Therefore, this study proposes an index model adapted to sociodemographic and econo- mic segments, inspired by the Index of Biotic Integrity (IBI). The methodology developed aims to assess the health of older adults in different groupingssuch as gender, ethnicity, and region by comparing them with so-called Reference Individuals (RI), defined in this study using statistical measures such as maximum, mean, and median. The application of the developed model resulted in the Relative Intrinsic Capacity Index (RICI), which expresses an individual’s value relative to the RI as a percentage. In the final analysis, the relationship between RICIs and the results of the Functional Ability questionnaires was examined, corroborating that individuals with better performance in Basic Activities of Daily Living (BADL) exhibited higher RICIs. Moreover, a positive Spearman correlation of 91.62% was observed between maximum RICIs and Instrumental Activities of Daily Li- ving (IADL), and 85.94% between median RICIs and Advanced Activities of Daily Living (AADL), within certain subgroups of the dataset. These findings reinforce the positive association between higher RICIs and better performance in functional abilities. Instituição: Universidade do Estado do Rio de Janeiro Tipo do documento: Dissertação Mon, 21 Jul 2025 00:00:00 GMT http://www.bdtd.uerj.br/handle/1/24755 2025-07-21T00:00:00Z