O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes. / The K-Shortest Path Problem is a generalization of the Shortest Path Problem, in which we must find the K paths between two vertices in a graph that have the lowest costs. We study some K-Shortest Path Problem algorithms applied to weighted directed graphs, allowing only paths with no repeated vertices. We compare empirically implementation of some algorithms, using instance graphs from the 9th DIMACS Implementation Challenge. We identify the strengths and weaknesses of each algorithm, and we propose a hybrid version of Feng\'s and Pascoal\'s algorithms. This proposed variant achieve better perfomance compared to both base algorithms in some graphs, and it is better than at least one of them in most cases.

The current methods used by forensic experts to analyse blood spatter neglects the influence of gravitation and drag on the trajectory of the droplet. This research attempts to suggest a more accurate method to determine the trajectory of a blood droplet using multi-target tracking. The multi-target tracking problem can be rewritten as a linear programming problem and solved by means of optimization and numerical methods. A literature survey is presented on relevant articles on blood spatter analysis and multi-target tracking. In contrast to a more advanced approach that assumes a background in probability, mathematical modelling and forensic science, this dissertation aims to give a comprehensive mathematical exposition of particle tracking. The tracking of multi-targets, through multi-target tracking, is investigated. The dynamic programming methods to solve the multi-target tracking are coded in the MATLAB programming language. Results are obtained for different scenarios and option inputs. Research strategies include studying documents, articles, journal entries and books. / MSc (Applied Mathematics), North-West University, Potchefstroom Campus, 2014

The current methods used by forensic experts to analyse blood spatter neglects the influence of gravitation and drag on the trajectory of the droplet. This research attempts to suggest a more accurate method to determine the trajectory of a blood droplet using multi-target tracking. The multi-target tracking problem can be rewritten as a linear programming problem and solved by means of optimization and numerical methods. A literature survey is presented on relevant articles on blood spatter analysis and multi-target tracking. In contrast to a more advanced approach that assumes a background in probability, mathematical modelling and forensic science, this dissertation aims to give a comprehensive mathematical exposition of particle tracking. The tracking of multi-targets, through multi-target tracking, is investigated. The dynamic programming methods to solve the multi-target tracking are coded in the MATLAB programming language. Results are obtained for different scenarios and option inputs. Research strategies include studying documents, articles, journal entries and books. / MSc (Applied Mathematics), North-West University, Potchefstroom Campus, 2014

Finding the shortest paths in a graph has been studied for a long time, and there are many main memory based algorithms dealing with this problem. Among these, Dijkstra's shortest path algorithm is one of the most commonly used efficient algorithms to the non-negative graphs. Even more efficient algorithms have been developed recently for graphs with particular properties such as the weights of edges fall into a range of integer. All of the mentioned algorithms require the graph totally reside in the main memory. Howevery, for very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), the requirement cannot be satisfied in most cases, so the algorithms mentioned above are not appropriate. My objective in this thesis is to design and evaluate the performance of external memory (disk-based) shortest path algorithms and data structures to solve the shortest path problem in very large digital maps. In particular the following questions are studied:What have other researchers done on the shortest path queries in very large digital maps?What could be improved on the previous works? How efficient are our new shortest paths algorithms on the digital maps, and what factors affect the efficiency? What can be done based on the algorithm? In this thesis, we give a disk-based Dijkstra's-like algorithm to answer shortest path queries based on pre-processing information. Experiments based on our Java implementation are given to show what factors affect the running time of our algorithms.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Pietro Poggi-Corradini / Caterina M. Scoglio / The modulus of a family of walks quanti es the richness of the family by favoring having many short walks over a few longer ones. In this dissertation, we investigate various families of walks to study new measures for quantifying network properties using modulus. The proposed new measures are compared to other known quantities. Our proposed method is based on walks on a network, and therefore will work in great generality. For instance, the networks we consider can be directed, multi-edged, weighted, and even contain disconnected parts. We study the popular centrality measure known in some circles as information centrality, also known as e ective conductance centrality. After reinterpreting this measure in terms of modulus of families of walks, we introduce a modi cation called shell modulus centrality, that relies on the egocentric structure of the graph. Ego networks are networks formed around egos with a speci c order of neighborhoods. We then propose e cient analytical and approximate methods for computing these measures on both directed and undirected networks. Finally, we describe a simple method inspired by shell modulus centrality, called general degree, which improves simple degree centrality and could prove to be a useful tool for practitioners in the applied sciences. General degree is useful for detecting the best set of nodes for immunization. We also study the structure of loops in networks using the notion of modulus of loop families. We introduce a new measure of network clustering by quantifying the richness of families of (simple) loops. Modulus tries to minimize the expected overlap among loops by spreading the expected link-usage optimally. We propose weighting networks using these expected link-usages to improve classical community detection algorithms. We show that the proposed method enhances the performance of certain algorithms, such as spectral partitioning and modularity maximization heuristics, on standard benchmarks. Computing loop modulus bene ts from e cient algorithms for nding shortest loops, thus we propose a deterministic combinatorial algorithm that nds a shortest cycle in graphs. The proposed algorithm reduces the worst case time complexity of the existing combinatorial algorithms to O(nm) or O(hkin2 log n) while visiting at most m - n + 1 cycles (size of cycle basis). For most empirical networks with average degree in O(n1􀀀 ) our algorithm is subcubic.

A classic problem Computational Geometry is finding all euclidean shortest paths in a simple polygon from a given source vertex to every other vertex in the boundary. In this text, we give a detailed description of the Visibility Graph and Shortest Path Tree structures that solve this problem and also present the Shortest Path Map structure that extends the solution to shortest paths to every point inside the polygon. / Um problema clássico em Geometria Computacional é: encontrar todos os caminhos mínimos euclidianos dentro de um polígono simples a partir de um dado vértice fonte para todos os outros vértices da borda. Neste texto, apresentamos detalhadamente as estruturas de Grafo de Visibilidade e Árvore de Caminhos Mínimos que resolvem este problema e descrevemos também a estrutura Mapa de Caminhos Mínimos que estende a solução para todos os pontos contidos dentro do polígono.

Cerný, em 1964, conjecturou que um autômato sincronizado com n estados possui uma palavra sincronizadora mínima de tamanho no máximo (n-1)². Esta conjectura permanece em aberto. Neste trabalho são apresentados algoritmos para obter palavras sincronizadoras e é feito um experimento comparativo entre os resultados obtidos por estes algoritmos em relação a algumas séries infinitas de autômatos. Por fim, é feito um breve histórico sobre os resultados parciais obtidos até a presente data e alguns destes trabalhos são apresentados em mais detalhes. / Cerný, on 1964, conjectured that a synchronizing automata with n states has a synchronizing word of size at most (n-1)². The conjecture remains open. We show some algorithms for obtaining synchronizing sequences and a comparative experiment between these algorithms with respect to some infinite series of automata. Furthermore, we briefly survey some of the partial results obtained until the present day.

O problema de caminhos mínimos (SP shortest path problem) é frequentemente colo- cado em prática em uma grande variedade de aplicações em diversas áreas. Nessas aplicações geralmente se deseja realizar algum tipo de deslocamento ou transporte entre dois ou mais pontos específicos em uma rede. Tal ação deve ser executada de forma ótima em relação a algum critério, por exemplo o menor custo possível, ou o menor gasto de tempo ou o máximo de confiabilidade/segurança. Na prática, muitas vezes não desejamos apenas o menor custo ou o menor tempo, mas desejamos otimizar uma combinação de diferentes critérios, por exemplo, um caminho que seja rápido e barato. Como não é possível otimizar sobre todos os critérios de uma só vez, nós escolhemos um dos critérios para representar a função custo, que será minimizada, e para os demais critérios representamos como recursos e definimos os limites que julgamos aceitáveis para o consumo de cada um desses recursos. Esta variação é cha- mada de problema de caminhos mínimos com restrições por recursos, ou como preferimos chamar, problema de caminhos mínimos com recursos limitados (RCSP resource constrained shortest path problem), o qual será o objeto de estudo neste trabalho. A adição de restrições por recursos no SP, infelizmente torna o problema NP-difícil, mesmo em grafos acíclicos, com restrições sobre um único recurso, e com todos os consu- mos de recursos positivos. Temos reduções dos famosos problemas N P-difíceis Mochila e Partição para o nosso problema. Em contextos diversos são encontrados problemas de cunho teórico e prático que po- dem ser formulados como problemas de caminhos mínimos com recursos limitados, o que nos motivou a estudá-lo a fim de desenvolver um trabalho que resumisse informações sufi- cientes para auxiliar pesquisadores ou desenvolvedores que tenham interesse no problema. Nós apresentamos aqui, uma detalhada revisão bibliográfica do RCSP, tendo como foco o desenvolvimento de algoritmos exatos para o caso onde possuímos um único recurso e a im- plementação e comparação dos principais algoritmos conhecidos, observando-os em situações práticas. / The problem of choosing a route to a trip, where we want minimize the distance of the path is a major problem in computing. In this basic form, this is the shortest path problem. But sometimes, besides the length we need to consider more parameters for selecting a good path. A common parameters to consider is the consumption of resources in a limited budget. A shortest path with these additional constraints is called resource constrained shortest path - RCSP. This paper has two main objectives: to present a literature review of the problem RCSP, focusing on exact algorithms for the case where we have a single resource, and implement and compare some algorithms, observing them in practical situations. The Shortest Path (SP) problem is among the fundamental problems of computer sci- ence. Its been deeply studied and subject of many publications. Also, many efficient solutions (polynomial time algorithms) are known for this problem. The SP is widely applied in many fields of science, not only computer science. These situations usually need to transport a load between two or more specific spots of a network. This action must be taken optimally regarding to some criterion, for instance the least cost, or the least time or maximum relia- bility. While new solutions for SP were presented, new demands were issued too, with new variations for the problem. One of these variations comes from the fact that, in a real scenario, a combination of many criteria must be optimized, for instance a path with least cost and least time. This problem is known as Multiobjective Shortest Path. Since its not possible to optimize all criteria at once, one of them is chosen to represent the cost function to be minimized and the others to represent resources with defined boundary. This variation, known as Resource Constrained Shortest Path (RCSP), was the object of the present study. By adding resource constraints, the SPbecomes N P-hard, even in acyclic graphs with only one resource constrained and all resource consumption being positive. There are reduc- tions from the famous NP-hard problems Knapsack and Partition to our problem. In many fields, are found theoretical and practical problems that may be expressed as a Resource Constrained Shortest Path Problem, which motivated us to study this problem in order to summarize enough information to researchers and developers involved with this problem. This paper presents a detailed bibliographic revision to RCSP, focusing on the development of exact algorithms for the case when there is only only one resource and on the implementation and comparison of the main known algorithms in practical situations.

Neste trabalho uma metodologia é proposta para disponibilizar, via internet, um serviço de roteirização de endereços para o campus da USP de Ribeirão Preto, com a determinação do menor caminho entre duas localidades. Esta metodologia pode ser aplicada não apenas ao campus da USP de Ribeirão Preto, mas ela poderá ser estendida às cidades e/ou regiões que possuam um mapa digital correspondente. Um sistema, denominado SIGRIB, foi desenvolvido para implementar a metodologia proposta. Utiliza o software ARCVIEW como suporte na manipulação de dados geográficos e cadastrais. Para facilitar a interação do usuário com o sistema SIGRIB, uma interface foi desenvolvida para que se possa fornecer duas localidades para as quais se deseja obter o menor caminho. O resultado desta consulta é uma figura ou conjunto de figuras contendo o menor caminho correspondente destacado. O sistema SIGRIB está disponível na internet (http://143.107.231.188/sigrib/pagina.asp) e vários testes são apresentados neste trabalho que demonstram o seu bom desempenho. / In this work a methodology is proposal to turn available, through internet, a routing service for addressing at campus of University of São Paulo, in Ribeirão Preto, including the determination of shortest way between two localities. This methodology can be applied not only to this campus but it can be extended to various cities and/or regions that have a corresponding digital map. A system, called SIGRIB, has been developed for implementing the proposed methodology. It utilizes ARCVIEW software as support for manipulation of geographical and cadastral data. To turn easy the interaction of user with SIGRIB system, a interface has been also implemented for that can provide two localities for which it desires to obtain the shortest path. The result of this search is a figure or set of figures containing the corresponding shortest path highlighted. The system SIGRIB is available in the internet (http://143.107.231.188/sigrib/pagina.asp) and several tests are presented in this work that demonstrate its good performance.

Este trabalho tem a finalidade de analisar a compatibilidade do gabarito dos caminhões brasileiros com a geometria das interseções urbanas de uma cidade de médio porte. Foi utilizado um Sistema de Informações Geográficas para a elaboração de rotas de menor caminho, dentro da área de estudo. Foram realizados levantamentos de campo para a reconstituição da geometria das interseções. Em seguida, através de um programa de simulação cada conversão necessária foi analisada para saber se havia a possibilidade de realização da manobra, dentro das rotas de menor caminho. / This work has the objective of analyzing the template compatibility, of Brazilian trucks with the urban intersections geometry in a medium-sized city. It was used a Geographic Information System to elaborate the shortest path within the study area. Field data were carried out for reconstitution of the intersections geometry. Next, each necessary conversion was analyzed, through a simulation program in order to know if the trucks were able to negotiate the curves in the shortest path routes.