Orientadores: Cid Carvalho de Souza, Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T06:06:38Z (GMT). No. of bitstreams: 1 Bogue_EduardoTheodoro_M.pdf: 1929433 bytes, checksum: 1c490811ba46f8482ede0d93da1163f8 (MD5) Previous issue date: 2014 / Resumo: Neste projeto, nós estudamos o Problema da Máxima Interseção de k-Subconjuntos (kMIS). Dado um inteiro k, um conjunto base U e uma coleção S de subconjuntos de U, o problema kMIS consiste em selecior k subconjuntos distintos S1, S2, ... , Sk em S cujo tamanho da interseção de |S1 ? S2 ? ... ? Sk| seja máxima. Trata-se de um problema NP-difícil e difícil de ser aproximado que ocorre em aplicações de áreas como biologia computacional e privacidade de dados. Até o nosso conhecimento, nenhum método exato foi proposto para resolver este problema. Neste trabalho, introduzimos cinco formulações de programação linear inteira para o problema, sendo três baseadas no método de Branch-and-Bound e duas no método de Branch-and-Cut. Além disso, uma heurística gulosa e uma meta-heurística GRASP foram desenvolvidas com o intuito de gerar bons limitantes inferiores. A heurística GRASP desenvolvida foi capaz de encontrar soluções muito próximas da solução ótima. Ademais, introduzimos um método muito eficiente de pré-processamento para reduzir o tamanho da entrada. Experimentos computacionais foram realizados de forma a analisar o desempenho dos modelos de programação linear inteira em questão, demonstrando que os modelos baseados no método de Branch-and-Cut obtiveram melhores resultados / Abstract: In this project, we study the Maximum k-Subset Intersection problem (kMIS). Given an integer k, a ground set U and a collection S of subsets of U, the kMIS problem is to select k distinct subsets S1, S2, ... , Sk in S whose intersection size |S1 ? S2 ? ... ? Sk| is maximum. The kMIS problem is NP-hard and hard to approximate and occurs in areas of applications such as computational biology and data privacy. To the best of our knowledge, no exact method was proposed to solve this problem. In this work, we introduce five integer linear programming formulations for the problem, three using a simple Branch-and-Bound method and two using a Branch-and-Cut method. We also present a greedy heuristic and a metaheuristic GRASP developed in order to generate good lower bounds. The heuristic GRASP developed was able to find solutions very close to the optimal ones. Furthermore, we introduce a very efficient preprocessing procedure to reduce the size of the input. Computational experiments were performed in order to analyze the performance of the integer linear programming models in question, showing that the Branch-and-Cut models performed better / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:59:09Z (GMT). No. of bitstreams: 1 Reis_MarcioFelix_M.pdf: 1988657 bytes, checksum: 6ee5ea6ba406aea3ccb7e3332e679eab (MD5) Previous issue date: 2014 / Resumo: Neste trabalho estudamos o problema da árvore geradora com muitas folhas (PAGMF). Este problema pode ser usado como abstração para diversos problemas práticos e sabe-se que é NP-difícil. Estudamos, implementamos e executamos testes para algoritmos aproximados e exatos para o PAGMF e para um caso particular que considera apenas grafos cúbicos. O principal objetivo do trabalho foi verificar o comportamento prático dos algoritmos estudados. Para as instâncias testadas, em geral, o algoritmo guloso apresentou melhores resultados para o PAGMF e o algoritmo 2-aproximado teve os melhores resultados para os grafos cúbicos / Abstract: In this work we study the maximum leaf spanning tree problem (MLSTP). This problem can be used as an abstraction for many practical problems and is known to be NP-hard. We studied, implemented and executed tests for approximate and exact algorithms for the MLSTP and for a particular case that considers only cubic graphs. The main objective of this study was to investigate the practical behavior of the algorithms studied. For the tested instances, in general, the greedy algorithm showed better results for the MLSTP and the 2-approximate algorithm had the best results for cubic graphs / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Célia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T10:47:23Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_D.pdf: 2015411 bytes, checksum: 4a6917f5811bde65dedbf0f7ab2577c5 (MD5) Previous issue date: 2011 / Resumo: Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida, será tratado o Problema de Empacotamento de Cliques, uma extensão do problema de emparelhamento máximo. Para a maioria das classes de grafos mais importantes, o problema é NP-Difícil. A contribuição apresentada resolve este problema em tempo polinomial (para qualquer tamanho fixo de clique) em grafos P4-arrumados, através de uma técnica similar a utilizada para os cografos. Infelizmente, para as superclasses mais estudadas da classe P4-arrumada, este problema é NP-Difícil, o que é um indício de que a técnica utilizada foi totalmente aproveitada em relação ás classes com poucos _P4's. Por fim, será estudado o Problema da Coloração Total Forte, uma variação do problema clássico da coloração total, que foi introduzido há pouco tempo e ainda tem sua complexidade computacional desconhecida. Como esperado, existem algoritmos polinomiais apenas para classes bastante simples de grafos. Além da complexidade, outro importante ponto em aberto para o problema é a conjectura de que o número de cores necessárias na solução do problema para um grafo G seria limitado por A(G) + 3. A técnica do pullback, já utilizada para os Problemas de Coloração de Arestas e Coloração Total em grafos dualmente cordais será estendida, resultando em um algoritmo linear para grafos indiferença (também conhecido como grafos de intervalos próprios). Este algoritmo produz uma solução que valida a conjectura nesta classe de grafos. Estas contribuições confirmam a importância da decomposição modular em algoritmos para classes de grafos com "poucos iYs" e ampliam o uso da técnica do pullback para variações dos problemas clássicos de coloração / Abstract: In this doctoral thesis, three problems on graphs are considered and results are given for them when the input is resctricted to some graph classes. All the problems are combinatorial optimization problems on simple graphs and have distinct classihcations of complexity. In two of them, the research focused on graph classes known as graphs with "few iVs" and on the use of modular decomposition on such graphs. In the last problem, a subclass of interval graphs was studied with respect to the application of the technique known as pullback. The first problem studied is the Minimal Separator Problem. For this problem, there exists polynomial time algorithms for every class of graphs which has a polynomial number of minimal separators. A linear-time algorithm, that lists all minimal separators of extended iVladen graphs, is presented. Moreover, tight bounds on the number and on the total size of minimal separators are given for extended iVladen graphs and for some of their subclasses: the iVladen, iVtidy, and iVlite graphs. This result extends a previous algorithm for iVspai'se graphs and gives, for the above classes, better bounds on the number of minimal separators that were already known to be polynomial. Then, the Clique Packing Problem is analyzed. The problem is an extension of the classical Maximum Matching Problem and is NP-Hard for almost all graph classes. The contribution presented solves the problem in polynomial time (for any fixed clique size) in iVtidy graphs through a technique similar to that used for cographs. However, the most well-known superclasses of iVtidy graphs contains split graphs, for which this problem is NP-Hard. This is an evidence that the technique was fully explored with respect of graph classes with few iVs. At last, the Strong Total Coloring Problem is considered. It is a recently introduced variation of the classical Total Coloring Problem and its complexity is still unknown. As expected, there are quite few graph classes for which the problem has a polynomial time algorithm. Besides its complexity, another important open question for this problem is a conjecture which states that A(G) + 3 colors are sufficient for coloring any graph G. A known technique, called pullback, used for edge and total coloring of dually chordal graphs is extended to derive a linear time algorithm for indifference graphs (also known as proper interval graphs). This algorithm produces solutions that validate the conjecture for this graph class. These contributions assert the importance of modular decomposition in algorithms for graph classes with "few P4's" and broaden the pullback technique to variations of classical coloring problems / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \begin{enumerate} \item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in $O(\log^2n)$ time. For a cut $(U, V\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| < |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \leq x \leq 2K$ with high probability in $O(|U|\log n)$ time. \item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\text{polylog}(n))$. For each node $v$ we require memory of size $\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of $O(n^2)$. \end{enumerate} / Graduate / 0984 / b_mountjoy9@hotmail.com

Orientadores: Siome Klein Goldenstein, Ricardo da Silva Torres / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T01:52:05Z (GMT). No. of bitstreams: 1 Rezende_RodrigoCarvalho_M.pdf: 3704794 bytes, checksum: 387c6f6ddc154e08ed8277b50d9a99df (MD5) Previous issue date: 2012 / Resumo: Esta dissertação estuda técnicas de Link Analysis para o problema de se calcular similaridade entre artigos acadêmicos organizados em uma biblioteca digital. Neste trabalho construímos um conjunto de dados e desenvolvemos um protocolo experimental para avaliar a eficácia das técnicas desenvolvidas. Para lidar com a alta complexidade dos algoritmos de similaridade para o nosso conjunto de dados, estudamos técnicas de amostragem de grafos e avaliamos objetivamente a qualidade das amostras geradas por estes métodos. A partir deste estudo, propomos um novo algoritmo de amostragem baseado na técnica Forest Fire. Experimentos realizados demonstram a superioridade do algoritmo de amostragem proposto. Além disso, apresenta-se uma nova meta-função de similaridade para artigos acadêmicos que considera apenas a informação de citação entre artigos, sem levar em conta o conteúdo textual e seus metadados para dizer o quanto um artigo é similar a outro. Esta meta-função transforma medidas de similaridade locais, como o coeficiente Jaccard e Adamic/Adar, em medidas recursivas, cuja similaridade depende recursivamente da similaridade de outros artigos relacionados, explorando a ideia de que dois artigos são mais similares na medida em que estão associados a artigos que também são similares. Para avaliação de eficácia do método proposto, criamos um gabarito de similaridade, que deriva da classificação hierárquica dos artigos no sistema de classificação de 1998 da Association for Computer Machinery (ACM). Este gabarito cria uma noção de similaridade tal que dois artigos são mais similares na medida em que são classificados em classes similares, isto é, que estão em classes hierarquicamente próximas. Experimentos são conduzidos no grafo de citação de artigos, extraído da biblioteca digital da ACM, contendo um subconjunto de 122.774 artigos e 523.699 arestas de citações, e comparam esta nova meta função de similaridade com o gabarito de similaridade e revelam que esta gera melhor eficácia que as medidas de similaridade locais consideradas. Além disso, avaliamos esta técnica na atividade prática de busca, por exemplo, e confirmamos que este meta-algoritmo melhora a eficácia das medidas locais consideradas / Abstract: These work studies techniques of Link Analysis used to address the problem of computing the similarity between academic papers organized in a digital library. We constructed a bibliographic dataset and developed an experimental protocol to evaluate the effectiveness of these techniques. To handle the high complexity of the similarity algorithms applied to our dataset, we study graph sampling techniques and evaluate the quality of the samples generated by these methods. This study lead to the proposal of a new sampling algorithm based on an existing technique named Forest Fire. Experiments results demonstrate the superiority of the proposed sampling algorithm. Moreover, we present a new metasimilarity function for scholarly articles that considers only the citation information, which does not take into account their textual content and its metadata, to compute how much an article is similar to another. This meta-function transforms local similarity measures, such as the Jaccard coefficient and Adamic/Adar, into recursive measures, whose similarity score recursively depends on the similarity of other related articles, exploring the idea that two articles are more similar if they are associated with articles which are also similar. To evaluate the effectiveness of the proposed method, we constructed a groundtruth of similarity, which derives from a hierarchical classification system of the Association for Computer Machinery (ACM). This groundtruth creates a notion of similarity such that two articles are more similar if they fall into similar classes (those that are hierarchically close to each other). Experiments are conducted in the citation graph, extracted from the ACM Digital Library, containing a subset of 122,774 articles and 523,699 citation edges. Obtained results demonstrate that this new meta-similarity function outperforms baselines. Furthermore, these results are confirmed in other experiments concerning the use of the proposed meta-functions in similarity search tasks / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

<div> Graph representation learning and Graph Neural Network (GNNs) models provide flexible tools for modeling and representing relational data (graphs) in various application domains. Specifically, node embedding methods provide continuous representations for vertices that has proved to be quite useful for prediction tasks, and Graph Neural Networks (GNNs) have recently been used for semi-supervised node and graph classification tasks with great success. </div><div> </div><div> However, most node embedding methods for unsupervised tasks consider a simple, sparse graph, and are mostly optimized to encode aspects of the network structure (typically local connectivity) with random walks. And GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels, which makes it not expressive enough for semi-supervised node classification tasks. </div><div> </div><div> This thesis will investigate methods to address these limitations, including: </div><div><br></div><div> (1) For heterogeneous graphs: Development of a method for dense(r), heterogeneous graphs that incorporates global statistics into the negative sampling procedure with applications in recommendation tasks;</div><div> (2) For capturing long-range role equivalence: Formalized notions of representation-based equivalence w.r.t regular/automorphic equivalence in a single graph or multiple graph samples, which is employed in a embedding-based models to capture long-range equivalence patterns that reflect topological roles; </div><div> (3) For collective classification: Since GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels, we develop an add-on collective learning framework to GNNs that provably boosts their expressiveness for node classification tasks, beyond that of an {\em optimal} WL-GNN, utilizing self-supervised learning and Monte Carlo sampled embeddings to incorporate node labels during inductive learning for semi-supervised node classification tasks.</div>

The problem discussed in this master's thesis is to increase the usability of aplication Classycle, especially to increase the comprehensibility of its outputs. Having studied theories of refactoring, testing, graphs and after thorough analysis of Classycle, it has been created new outputs of the application, displaying the output data in graphics form. The application has been tested with real-life data and it is ready to be deploy in company. Thanks to creation of new forms of outputs, which are discribed in practical part of master's thesis, programmer obtains a powerful tool for detection dependences between classes and packages in code.

This master thesis deals with the planning of the robot's path using selected graph algorithms of artificial intelligence. The theoretical part describes the basic methods of planning a robot's path. It is related to the graph algorithm more closely. The practical part deals with implementation of selected graph algorithms, creation of simulation environment in Python, description and evaluation of experiments.

<div>We consider the maximum vertex-weighted matching problem (MVM), in which non-negative weights are assigned to the vertices of a graph, and the weight of a matching is the sum of the weights of the matched vertices. Vertex-weighted matchings arise in many applications, including internet advertising, facility scheduling, constraint satisfaction, the design of network switches, and computation of sparse bases for the null space or the column space of a matrix. Let m be the number of edges, n number of vertices, and D the maximum degree of a vertex in the graph. We design two exact algorithms for the MVM problem with time complexities of O(mn) and O(Dmn). The new exact algorithms use a maximum cardinality matching as an initial matching, after which the weight of the matching is increased using weight-increasing paths.</div><div><br></div><div>Although MVM problems can be solved exactly in polynomial time, exact MVM algorithms are still slow in practice for large graphs with millions and even billions of edges. Hence we investigate several approximation algorithms for MVM in this thesis. First we show that a maximum vertex-weighted matching can be approximated within an approximation ratio arbitrarily close to one, to k/(k + 1), where k is related to the length of augmenting or weight-increasing paths searched by the algorithm. We identify two main approaches for designing approximation algorithms for MVM. The first approach is direct; vertices are sorted in non-increasing order of weights, and then the algorithm searches for augmenting paths of restricted length that reach a heaviest vertex. (In this approach each vertex is processed once). The second approach repeatedly searches for augmenting paths and increasing paths, again of restricted length, until none can be found. In this second, iterative approach, a vertex may need to be processed multiple times. We design two approximation algorithms based on the direct approach with approximation ratios of 1/2 and 2/3. The time complexities of the 1/2-approximation algorithm is O(m + n log n), and that of the 2/3-approximation algorithm is O(mlogD). Employing the second approach, we design 1/2- and 2/3-approximation algorithms for MVM with time complexities of O(Dm) and O(D²m), respectively. We show that the iterative algorithm can be generalized to nd a k/(k+1)-approximate MVM with a time complexity of O(D^km). In addition, we design parallel 1/2- and 2/3-approximation algorithms for a shared memory programming model, and introduce a new technique for locking augmenting paths to avoid deadlock and related problems. </div><div><br></div><div>MVM problems may be solved using algorithms for the maximum edge-weighted matching (MEM) by assigning to each edge a weight equal to the sum of the vertex weights on its endpoints. However, our results will show that this is one way to generate MEM problems that are difficult to solve. On such problems, exact MEM algorithms may require run times that are a factor of a thousand or more larger than the time of an exact MVM algorithm. Our results show the competitiveness of the new exact algorithms by demonstrating that they outperform MEM exact algorithms. Specifically, our fastest exact algorithm runs faster than the fastest MEM implementation by a factor of 37 and 18 on geometric mean, using two different sets of weights on our test problems. In some instances, the factor can be higher than 500. Moreover, extensive experimental results show that the MVM approximation algorithm outperforms an MEM approximation algorithm with the same approximation ratio, with respect to matching weight and run time. Indeed, our results show that the MVM approximation algorithm outperforms the corresponding MEM algorithm with respect to these metrics in both serial and parallel settings.</div>