The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark paradigm. The new heuristic’s novel feature is that it computes and stores a reduced amount of preprocessed information (in comparison to previous landmark-based algorithms) while enabling more informed search decisions. We demonstrate that domination of this heuristic over its predecessor depends on landmark selection and that, in general, the denser the landmark set, the better heuristic performs. Due to the reduced memory requirement, this new heuristic admits much denser landmark sets. We conduct experiments to characterize the impact that landmark configurations have on this new heuristic, demonstrating that centrality-based landmark selection has the best tradeoff between preprocessing and runtime. Using a developed graph library and static information from benchmark road map datasets, the algorithm is compared experimentally with previous landmark-based shortest path techniques in a fixed-memory environment to demonstrate a reduction in overall computational time and memory requirements. Experimental results are evaluated to detail the significance of landmark selection and density, the tradeoffs of performing preprocessing, and the practical use cases of the algorithm.

We interpret the generalised gauge symmetry introduced in string theory and M-Theory as a special case of Grothendieck's stability equivalence relation in the definition of the 0th K-group and we calculate the Euler number of the elliptic de Rham complex twisted by a flat connection. Then using Polyakov's classical equivalence of flat bundles with non-linear sigma models we define a new topological invariant for foliations using techniques from noncommutative geometry, in particular the Connes' pairing between K-Theory and cyclic cohomology. This new invariant classifies foliations up to Morita equivalence.

Einstein's field equations are a system of ten partial differential equations. For a special class of spacetimes known as Gowdy spacetimes, the number of equations is reduced due to additional structure of two dimensional isometry groups with mutually orthogonal Killing vectors. In this thesis, we focus on a particular model of Gowdy spacetimes known as the polarized T3 model, and provide an explicit solution to Einstein's equations.

Quandles, which are algebraic structures related to knots, can be used to color knot diagrams, and the number of these colorings is called the quandle coloring invariant. We strengthen the quandle coloring invariant by considering a graph structure on the space of quandle colorings of a knot, and we call our graph the quandle coloring quiver. This structure is a categorification of the quandle coloring invariant. Then, we strengthen the quiver by decorating it with Boltzmann weights. Explicit examples of links that show that our enhancements are proper are provided, as well as background information in quandle theory.

The purpose of this project was to study the differential geometry of curves and surfaces in three-dimensional Euclidean space. Some important concepts such as, Curvature, Fundamental Form, Christoffel symbols, and Geodesic Curvature and equations are explored.

This thesis consists of two main chapters along with an introduction andconclusion. In the introduction, we address the inspiration for the thesis, whichoriginates in a common calculus problem wherein travel time is minimized across two media separated by a single, straight boundary line. We then discuss the correlation of this problem with physics via Snells Law. The first core chapter takes this idea and develops it to include the concept of two media with a circular border. To make the problem easier to discuss, we talk about it in terms of running and swimming speeds. We first address the case where the starting and ending points for the passage are both on the boundary. We find the possible optimal paths, and also determine the conditions under which we travel along each path. Next we move the starting point to a location outside the boundary. While we are not able to determine the exact optimal path, we do arrive at some conclusions about what does not constitute the optimal path. In the second chapter, we alter this problem to address a rectangular enclosed boundary, which we refer to as a swimming pool. The variations in this scenario prove complex enough that we focus on the case where both starting and ending points are on the boundary. We start by considering starting and ending points on adjacent sides of the rectangle. We identify three possibilities for the fastest path, and are able to identify the conditions that will make each path optimal. We then address the case where the points are on opposite sides of the pool. We identify the possible paths for a minimum time and once again ascertain the conditions that make each path optimal. We conclude by briefly designating some other scenarios that we began to investigate, but were not able to explore in depth. They promise insightful results, and we hope to be able to address them in the future.

In the study of list colorings of graphs, we assume each vertex of a graph has a specified list of colors from which it may be colored. For planar graphs, it is known that there is a coloring for any list assignment where each list contains five colors. If we have some vertices that are precolored, can we extend this to a coloring of the entire graph? We explore distance constraints when we allow the lists to contain an extra color. For lists of length five, we fix $W$ as a subset of $V(G)$ such that all vertices in $W$ have been assigned colors from their respective lists. We give a new, simplified proof where there are a small number of precolored vertices on the same face. We also explore cases where $W=\{u,v\}$ and $G$ has a separating $C_3$ or $C_4$ between $u$ and $v$.

The goal of the thesis is to study geodesics on surfaces of constant Gaussian curvature. The first three sections of the thesis is dedicated to the definitions and theorems necessary to study surfaces of constant Gaussian curvature. The fourth section contains examples of geodesics on these types of surfaces and discusses their properties. The thesis incorporates the use of Maple, a mathematics software package, in some of its calculations and graphs. The thesis' conclusion is that the Gaussian curvature is a surface invariant and the geodesics of these surfaces will be the so-called best paths.

This thesis covers improvements on the upperbounds for ropelength of a specific class of algebraic knots.

Orientador: Weber Flávio Pereira / Resumo: A Teoria dos Sistemas Dinâmicos pode ser aplicada em diversas áreas da ciência, para, por exemplo, modelar fenômenos e problemas: Biológicos, da Física, Mecânica, Eletrônica, Economia, etc. Um sistema pode ser definido como um conjunto de elementos agrupados que mantêm alguma interação, de modo que existam relações de causa e efeito. Dizemos que é dinâmico quando algumas grandezas que compõem os elementos variam no tempo, sendo o tempo discreto quando a variável tempo é um número inteiro. Na busca de uma compreensão qualitativa e/ou topológica de um sistema, revela-se uma gama muito grande de movimentos que podem ser tanto regulares quanto caóticos. O termo “caos” só foi introduzido por James Yorke e TienYien Li em 1975, num artigo que simplificava um dos resultados da escola russa: o Teorema de Sharkovskii de 1964. Esporadicamente, antes e depois da introdução do termo, os sistemas caóticos apareciam na literatura aplicada, o mais famoso deles foi por Edward Norton Lorenz em 1963, que se propôs a modelar a convecção atmosférica. Em seus estudos ele descobriu que, para o seu modelo matemático, ínfimas modificações nas coordenadas iniciais mudavam de forma significativa os resultados finais, daí originou o termo popular do fenômeno (Efeito Borboleta). Mais tarde, em 1989, Robert Luke Devaney no seu livro: “An Introduction to Chaotic Dynamical Systems” [11], definiu um sistema como caótico se ele tem uma dependência sensível das condições iniciais, é topologicamente transitivo e suas ... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Dynamical Systems Theory can be applied in various areas of science, for example, to model phenomena and problems: biology, physics, mechanics, electronics, economics, etc. A system can be defined as a set of grouped elements that maintain someinteraction. Wesaythatitisdynamicwhensomemagnitudesthatmakeupthe elementsvaryintime,beingdiscretetimewhenthevariabletimeisaninteger. Inthe pursuit of a qualitative and/or topological understanding of a system, a wide range of movements that can be both regular or chaotic is revealed. The term “chaos” was only introduced by James Yorke and TienYien Li in 1975, in an article that simplified one of the results of the Russian school: the 1964 Sharkovskii’s Theorem. Sporadically, before and after the introduction of the term, chaotic systems appeared in applied literature, the most famous of which was by Edward Norton Lorenz in 1963, who set out to model atmospheric convection. In his studies he found that for his created system, minor modifications to the initial coordinates significantly changed the final results, hence the popular term of the phenomenon (Butterfly Effect). Later, in 1989, Robert Luke Devaney in his book, “An Introduction to Chaotic Dynamical Systems” [11], defined a system as chaotic if it has a sensitive dependence on initial conditions, is topologically transitive, and its periodic orbits form a dense set. The main objective of this work is to study and present the evolution of the definition of discrete time Chaotic Dynamic Sy... (Complete abstract click electronic access below) / Mestre