Um emparelhamento em um grafo é um conjunto de arestas duas a duas não adjacentes. Dado um grafo G com pesos em suas arestas, o problema do emparelhamento de peso é máximo é encontrar um emparelhamento cuja soma dos pesos de suas arestas é máxima. Neste trabalho estudamos diferentes soluções para esse problema. Estudamos algoritmos combinatórios que resolvem o problema no caso em que G é bipartido e no caso geral. O algoritmo de Edmonds é um algoritmo polinomial cuja complexidade de tempo é O(n^4), onde n é o número de vértices do grafo G. Discutimos nesse trabalho nossa implementação desse algoritmo. Num trabalho de 1985, Grötschel e Holland propuseram o uso de ferramentas de programação linear para resolver o mesmo problema. O método chamado de planos-de-corte baseia-se em um resultado de Padberg e Rao de que o problema da separação associado ao poliedro dos emparelhamentos pode ser resolvido em tempo polinomial. Neste trabalho fizemos implementações dos dois métodos e os utilizamos para resolver diversos tipos de instâncias do problema. Nossa conclusão é que o método poliédrico, apesar de utilizar ferramentas genéricas, é bastante eficiente na prática. / A matching in a graph G is a set of pairwise disjoint edges of G. Given a graph G with edge weights, we define the maximum weight matching problem as that of finding a matching which maximizes the sum of its weights. In this thesis we study different solutions to this problem. We studied combinatorial algorithms that solve this problem in the case where G is bipartite and also in the general case. Edmonds algorithm [Edm65a] is a polynomial time algorithm with complexity O(n4 ), where n is the number of vertices in the graph G. We discuss in this document our implementation of this algorithm. In a paper from 1985, Gr tschel & Holland [GH85] discussed the use of linear programming o tools for solving the maximum weight matching problem. This so called cut-plane method relies on a result by Padberg & Rao [PR82] that proves that the separation problem associated with matching polyhedron is solvable in polinomial time. In this work we implemented both methods and used then to solve different instances of the problem. Our conclusion is that the polyhedral method, although using generical tools is very efficient in practice.

O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta. / Irregular nesting belongs to the area of cutting and packing problems and are employed in the textile, wood and shipbuilding industries. The problem consists in determining a configuration for a set of irregular items which minimizes the length of the rectangular container in which the layout is located. The solution must be feasible, i.e., items must not overlap nor protrude the container walls. Due to practical reasons, up to four orientations are allowed for an item. The volume of wasted material is directly affected by the quality (density) of the layout. Thus, an efficient solution produces a positive economic and environmental impact. In this work, the objective is to automatically obtain layouts such that their density and the performance of the algorithm are competitive with other solutions in literature. So as to achieve this goal, two approaches are proposed. The first method uses a special sequential placement heuristic such that the algorithm maximizes exact placements, which consist of constrained positions for items. In general terms, a search is performed in the placement sequence in order to obtain a compact layout. In the second approach, which is the main subject of this work, raster methods are employed to guide the translation of items, which are free to move within the layout, and may overlap other items. The method is based on overlap minimization techniques, in which the objective is to eliminate the overlap in a fixed dimensions container. Both algorithms were tested using benchmark problems from the literature. The first strategy yielded unsatisfactory results, though it provided important information about the properties of exactly fitting placements. On the other hand, the main approach was able to produce competitive solutions. The performance was also compatible with other solutions, even in cases which the data volume was high. Moreover, as a future work, an extension for the algorithm can be developed such that items with generic geometry can be considered, which would be an important advance in research terms.

The aim of this work is to investigate some algebraic and combinatorial aspects of group factorizations. The main contribution of this dissertation is a set of new results regarding factorization of groups, with emphasis on the nonabelian case. We introduce a novel technique for factorization of groups, the so-called free mappings, a powerful tool for factorization of a wide class of abelian and non-abelian groups. By applying a certain group action on the blocks of a factorization, a number of combinatorial and computational problems were noted and studied. In particular, we analyze the case of the group Aut(Zn) acting on blocks of factorization of Zn. We present new theoretical facts that reveal the numerical structure of the stabilizer of a set in Zn, under the action of Aut(Zn). New algorithms for finding the stabilizer of a set and checking whether two sets belong to the same orbit are proposed. / by Vladimir Bozovic. / Thesis (Ph.D.)--Florida Atlantic University, 2008. / Includes bibliography. / Electronic reproduction. Boca Raton, FL : 2008 Mode of access: World Wide Web.

The subject of this thesis is the asymptotic behaviour of generating functions of different combinatorial models of two-dimensional lattice walks and polygons, enumerated with respect to different parameters, such as perimeter, number of steps and area. These models occur in various applications in physics, computer science and biology. In particular, they can be seen as simple models of biological vesicles or polymers. Of particular interest is the singular behaviour of the generating functions around special, so-called multicritical points in their parameter space, which correspond physically to phase transitions. The singular behaviour around the multicritical point is described by a scaling function, alongside a small set of critical exponents. Apart from some non-rigorous heuristics, our asymptotic analysis mainly consists in applying the method of steepest descents to a suitable integral expression for the exact solution for the generating function of a given model. The similar mathematical structure of the exact solutions of the different models allows for a unified treatment. In the saddle point analysis, the multicritical points correspond to points in the parameter space at which several saddle points of the integral kernels coalesce. Generically, two saddle points coalesce, in which case the scaling function is expressible in terms of the Airy function. As we will see, this is the case for Dyck and Schröder paths, directed column-convex polygons and partially directed self-avoiding walks. The result for Dyck paths also allows for the scaling analysis of Bernoulli meanders (also known as ballot paths). We then construct the model of deformed Dyck paths, where three saddle points coalesce in the corresponding integral kernel, thereby leading to an asymptotic expression in terms of a bivariate, generalised Airy integral.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Bibliography: leaves 100-102. / by Robert Alan Proctor. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Bibliography: p. 135-138. / by James William Walker. / Ph.D.

Thesis. 1977. Ph.D.--Massachusetts Institute of Technology. Dept. of Mathematics. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Vita. / Bibliography : leaves 104-110. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1979. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND SCIENCE. / Vita. / Bibliography: leaves 74-75. / Ph.D.

No description available.

No description available.