No description available.

In recent years, concerns of privacy have become more prominent for social networks. Anonymizing a graph meaningfully is a challenging problem, as the original graph properties must be preserved as well as possible. We introduce a generalization of the degree anonymization problem posed by Liu and Terzi. In this problem, our goal is to anonymize a given subset of vertices in a graph while adding the fewest possible number of edges. We examine different approaches to solving the problem, one of which finds a degree-constrained subgraph to determine which edges to add within the given subset and another that uses a greedy approach that is not optimal, but is more efficient in space and time. The main contribution of this thesis is an efficient algorithm for this problem by exploring its connection with the degree-constrained subgraph problem. Our experimental results show that our algorithms perform very well on many instances of social network data. / Graduate

One of the most important factors on the success of evolutionary algorithms (EAs) about trees is the representation of them. The representation should exhibit efficiency, locality and heritability to enable effective evolutionary computing. Neville proposed three different methods for encoding labeled trees. The first one is similar with Pr&uuml / fer&#039 / s encoding. In 2001, it is reported that, the use of Pr&uuml / fer numbers is a poor representation of spanning trees for evolutionary search, since it has low locality for random trees. In the thesis Neville&#039 / s other two encodings, namely Neville branch numbers and Neville leaf numbers, are studied. For their performance in EA their properties and algorithms for encoding and decoding them are also examined. Optimal algorithms with time and space complexities of O(n) , where n is the number of nodes, for encoding and decoding Neville branch numbers are given. The localities of Neville&#039 / s encodings are investigated. It is shown that, although the localities of Neville branch and leaf numbers are perfect for star type trees, they are low for random trees. Neville branch and Neville leaf numbers are compared with other codings in EAs and SA for four problems: &#039 / onemax tree problem&#039 / , &#039 / degree-constrained minimum spanning tree problem&#039 / , &#039 / all spanning trees problem&#039 / and &#039 / all degree constrained spanning trees problem&#039 / . It is shown that, neither Neville nor Pr&uuml / fer encodings are suitable for EAs. These encodings are suitable for only tree enumeration and degree computation. Algorithms which are timewise and spacewise optimal for &#039 / all spanning trees problem&#039 / (ASTP) for complete graphs, are given by using Neville branch encoding. Computed time and space complexities for solving ASTP of complete graphs are O(nn-2) and O(n) if trees are only enumerated and O(nn-1) and O(n) if all spanning trees are printed , respectively, where n is the number of nodes. Similarly, &#039 / all degree constrained spanning trees problem&#039 / of a complete graph is solvable in O(nn-1) time and O(n) space.

Made available in DSpace on 2014-12-17T15:47:45Z (GMT). No. of bitstreams: 1 GivanaldoRS.pdf: 1524067 bytes, checksum: d73e18e4ae3a0bffab7711efc808bffa (MD5) Previous issue date: 2006-05-19 / Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approaches / Os problemas de otimiza??o combinat?ria t?m como objetivo maximizar ou minimizar uma fun??o definida sobre um certo dom?nio finito. J? as metaheur?sticas s?o procedimentos destinados a encontrar uma boa solu??o, eventualmente a ?tima, consistindo na aplica??o de uma heur?stica subordinada, a qual tem que ser modelada para cada problema espec?fico. Este trabalho apresenta algoritmos baseados na t?cnica de otimiza??o por nuvem de part?culas (metaheur?stica) para dois problemas de otimiza??o combinat?ria: o Problema do Caixeiro Viajante e o Problema da ?rvore Geradora M?nima Restrita em Grau Multicrit?rio. O primeiro ? um problema em que apenas um objetivo ? otimizado, enquanto o segundo ? um problema que deve lidar com m?ltiplos objetivos. Os algoritmos propostos s?o comparados a outras abordagens para o mesmo problema em quest?o, em termos de qualidade de solu??o, a fim de verificar a efici?ncia desses algoritmos