<p>Smart downlink scheduling can be used to reduce infrastructure-to-vehicle energy costs in delay tolerant roadside networks. In this thesis this type of scheduling is incorporated into ON/OFF roadside unit sleep activity, to further reduce infrastructure power consumption. To achieve significant power savings however, the OFF-to-ON sleep transitions may be very lengthy, and this overhead must be taken into account when performing the scheduling. The OFF/ON sleep transitions are incorporated into a lower bound on energy use for the constant bit rate air interface case. An online scheduling algorithm referred to as the Flow Graph Sleep Scheduler (FGS) is then introduced which makes locally optimum ON/OFF cycle decisions. This is done by computing energy estimates needed both with and without a new OFF/ON cycle. The energy calculation can be efficiently done using a novel minimum ow graph formulation. We also consider the fixed transmit power, variable bit rate, air interface case. As before, a lower bound on RSU energy use is computed by formulating and solving an integer program. Results from a variety of experiments show that the proposed scheduling algorithms perform well when compared to the energy lower bounds. The algorithms are especially attractive in situations where vehicle demands and arrival rates are such that the energy costs permit frequent ON/OFF cycling.</p> / Master of Science (MSc)

This thesis deals with toric ideals associated with finite simple graphs. In particular we establish some results pertaining to the nature of the generators and syzygies of toric ideals associated with finite simple graphs. The first result dealt with in this thesis expands upon work by Favacchio, Hofscheier, Keiper, and Van Tuyl which states that for G, a graph obtained by "gluing" a graph H1 to a graph H2 along an induced subgraph, we can obtain the toric ideal associated to G from the toric ideals associated to H1 and H2 by taking their sum as ideals in the larger ring and saturating by a particular monomial f. Our contribution is to sharpen the result and show that instead of a saturation by f, we need only examine the colon ideal with f^2. The second result treated by this thesis pertains to graded Betti numbers of toric ideals of complete bipartite graphs. We show that by counting specific subgraphs one can explicitly compute a minimal set of generators for the corresponding toric ideals as well as minimal generating sets for the first two syzygy modules. Additionally we provide formulas for some of the graded Betti numbers. The final topic treated pertains to a relationship between the fundamental group the finite simple graph G and the associated toric ideal to G. It was shown by Villareal as well as Hibi and Ohsugi that the generators of a toric ideal associated to a finite simple graph correspond to the closed even walks of the graph G, thus linking algebraic properties to combinatorial ones. Therefore it is a natural question whether there is a relationship between the toric ideal associated to the graph G and the fundamental group of the graph G. We show, under the assumption that G is a bipartite graph with some additional assumptions, one can conceive of the set of binomials in the toric ideal with coprime terms, B(IG), as a group with an appropriately chosen operation ⋆ and establish a group isomorphism (B(IG), ⋆) ∼= π1(G)/H where H is a normal subgroup. We exploit this relationship further to obtain information about the generators of IG as well as bounds on the Betti numbers. We are also able to characterise all regular sequences and hence compute the depth of the toric ideal of G. We also use the framework to prove that IG = (⟨G⟩ : (e1 · · · em)^∞) where G is a set of binomials which correspond to a generating set of π1(G). / Thesis / Doctor of Philosophy (PhD)

This work addresses two novel problems in the field of computational genomics. The first is whole genome alignment and the second is inferring horizontal gene transfer using posets. We define these two problems and present algorithmic approaches for solving them. For the whole genome alignment, we define alignment graphs for representing different evolutionary events, and define a scoring function for those graphs. The problem defined is proven to be NP-complete. Two heuristics are presented to solve the problem, one is a dynamic programming approach that is optimal for a class of sequences that we define in this work as breakable arrangements. And, the other is a greedy approach that is not necessarily optimal, however, unlike the dynamic programming approach, it allows for reversals. For inferring horizontal gene transfer, we define partial order sets among species, with respect to different genes, and infer genes involved in horizontal gene transfer by comparing posets for different genes. The posets are used to construct a tree for each gene. Those trees are then compared and tested for contradiction, where contradictory trees correspond to genes that are candidates of horizontal gene transfer. / Ph. D.

<p>The Powder Bed Fusion (PBF) process is increasingly employed by industry to fabricate complex parts with stringent standard criteria. However, fabricating parts free of defects using this process is still a major challenge. As reported in the literature, thermally induced abnormalities form the majority of generated defects and are largely attributed to thermal evolution. Various methodologies have been introduced in the literature to eliminate or mitigate such abnormalities. However, most of these methodologies are post-process in nature, lacking adaptability and customization to accommodate different geometries or materials. Consequently, they fall short of adequately addressing these challenges. Monitoring and controlling temperature, along with its distribution throughout each layer during fabrication, is an effective and efficient proxy to control the thermal evolution of the process. This, in turn, provides a real-time solution to effectively overcome such challenges. </p> <p>The objective of this dissertation is to introduce a novel online thermography and closedloop hybrid-control (NOTCH)©, an ultra-fast and practical control approach, to modify the scan strategy in metal PBF in real time. This methodology employs different mathematical-thermophysical concept-based or thermophysical-based models combined with optimization algorithms designed to optimize the printing sequence of islands/stripes/zones in order to avoid or mitigate residual stress and distortion. This methodology is adaptable to different geometries, dimensions, and materials, and is capable of being used with machines having varying ranges of specifications. </p> <p>NOTCH’s objective is to achieve a uniform temperature distribution throughout an entire layer and through the printed part (between layers) to mitigate residual stress and thermally related distortion. To attain this objective, this study explores modifying or optimizing the printing sequence of islands/stripes in an island or the strip scanning strategy. This dissertation presents three key contributions: </p> <p>First, this work introduces two potential models: the Genetic Algorithm Maximum Path (GAMP) strategy and Generalized Advanced Graph Theory. Preliminary results for a printed/simulated prototype are presented. These models, along with the Tessellation algorithm (developed in my M.Sc. thesis), were employed within NOTCH.</p> <p>Second, I developed two optimization algorithms based on the greedy and evolutionary approaches. Both algorithms are direct-derivative-free methods. The greedy optimization provides a definitive solution at each printing step, selecting the island/stripe that ensures the highest temperature uniformity. Conversely, the evolutionary algorithm seeks to obtain the final optimal solution at the end of the printing process, i.e., the printing sequence with the highest uniformity in the last printing step. This approach is inspired by the concept of Random Search algorithms, offering a non-definitive solution to find an optimal solution. </p> <p>Last, this work presents the NOTCH methodology, enabling real-time modification of printing sequences through the integration of a novel thermography methodology (developed in my M.Sc. thesis), developed models, and optimization algorithms.</p> <p><br></p>

No / Both prominent feature points and geodesic distance are key factors for mesh segmentation. With these two factors, this paper proposes a graph cut based mesh segmentation method. The mesh is first preprocessed by Laplacian smoothing. According to the Gaussian curvature, candidate feature points are then selected by a predefined threshold. With DBSCAN (Density-Based Spatial Clustering of Application with Noise), the selected candidate points are separated into some clusters, and the points with the maximum curvature in every cluster are regarded as the final feature points. We label these feature points, and regard the faces in the mesh as nodes for graph cut. Our energy function is constructed by utilizing the ratio between the geodesic distance and the Euclidean distance of vertex pairs of the mesh. The final segmentation result is obtained by minimizing the energy function using graph cut. The proposed algorithm is pose-invariant and can robustly segment the mesh into different parts in line with the selected feature points.

Netzwerke stellen einen integralen Bestandteil unseres Lebens dar. Eines der wichtigsten Kommunikations-Netzwerke ist das Internet, welches zu starken Veränderungen im Alltag geführt hat. Diese werden in Teilaspekten in der vorliegenden Dissertation untersucht. Insgesamt ist die Dissertation in drei Bereiche unterteilt, welche auf der traditionellen Perspektive der drei Dimensionen von Informationssystemen basieren. Diese Dimensionen umfassen die Technologie, das Management und die Organisation. Im Zentrum der Dissertation steht hierbei die Technologie-Dimension in dessen Rahmen die Struktur und Robustheit des Internets sowie anderer Netzwerke unter Nutzung des mathematisch-methodischen Aspekts der Graphentheorie analysiert werden. Der zweite Teilbereich der vorliegenden Arbeit wechselt die Perspektive hin zum Management. Unter Nutzung von Methoden der prädikativen Modellierung stehen das bessere Verständnis und die Möglichkeit der Vorhersage von Nutzerverhalten im E-Commerce-Kontext im Fokus. Der dritte Bereich umfasst die Organisations-Perspektive aus Sicht der Nutzer. Hierbei werden zwei spezielle Unterbereiche betrachtet. Der erste Unterbereich umfasst Webseiten Sozialer Medien und analysiert wie verschiedene Nutzergruppen diese verwenden. Der zweite Unterbereich befasst sich mit dem Einfluss der weitläufigen Verbreitung von mobilen Endgeräten auf Aspekte des persönlichen und beruflichen Lebens von Individuen. Aufbauend auf diesen drei Dimensionen wurden im Rahmen dieser Dissertation insgesamt 18 Studien durchgeführt, die sich unterschiedlicher methodischer Anwendungen bedienen um wissenschaftliche Erkenntnisse zu den vorgestellten Teilbereichen zu erlangen. / Networks constitute an integral part of our lives. One of the most important communication networks is the Internet which led to large changes in everyday life, which are examined in part in this dissertation. Overall, the present dissertation is subdivided into three areas, which are based on the traditional three dimensions of information systems, comprising perspectives technology, management and organization. At the core of this dissertation is the technological perspective, centered on an analysis of the structure and robustness of the Internet network using the mathematical-methodical aspect of graph theory. The second part of the thesis deals with the management perspective. The focus lies on the understanding and prediction of user behavior in the e-commerce context utilizing methods of predictive modeling. The third area includes the organizational perspective from the point of view of users. Here, two specific sub-areas are selected. The first sub-area revolves around social media websites, with the goal of understanding how sub-groups of users utilize them in different ways. The second area is centered around the aspect of how the propagation of mobile devices influences individuals in their personal and professional environments. Based on these three perspectives, a total of 18 studies were conducted within the scope of this dissertation, using different methodological applications to gain scientific insights with respect to the areas examined.

Viele Probleme der Kombinatorik, Zahlentheorie, Wahrscheinlichkeitstheorie, Zuverlässigkeitstheorie und Statistik lassen sich durch Anwendung einer einheitlichen Methode lösen, die als Prinzip der Inklusion-Exklusion bekannt ist. Das Prinzip der Inklusion-Exklusion drückt die Indikatorfunktion einer Vereinigung endlich vieler Ereignisse als alternierende Summe der Indikatorfunktionen ihrer Durchschnitte aus. Die vorliegende Schrift befasst sich mit verbesserten Inklusions-Exklusions-Identitäten und verbesserten Bonferroni-Ungleichungen, die voraussetzen, dass die Ereignisfamilie gewissen strukturellen Anforderungen genügt. Solche wohl-strukturierten Ereignisfamilien finden sich u.a. in der schließenden Statistik, der kombinatorischen Zuverlässigkeitstheorie und der chromatischen Graphentheorie. / Many problems in combinatorics, number theory, probability theory , reliability theory and statistics can be solved by applying a unifying method, which is known as the principle of inclusion-exclusion. The principle of inclusion-exclusion expresses the indicator function of a union of finitely many events as an alternating sum of indicator functions of their intersections. This thesis deals with improved inclusion-exclusion identities and improved Bonferroni inequalities that require the family of events to satisfy some structural restrictions. Examples of such well-structured families arise in problems of statistical inference, combinatorial reliability theory and chromatic graph theory.

Component failures can result in catastrophic behaviors in safety critical embedded systems, sometimes resulting in loss of life. Component failures can be treated as off nominal behaviors (ONBs) with respect to the components and sub systems involved in an embedded system. A lot of research is being carried out to tackle the problem of ONBs. These approaches are mainly focused on the states (i.e., desired and undesired states of a system at a given point of time to detect ONBs). In this paper, an approach is discussed to detect component failures and critical components of an embedded system. The approach is based on fault tree analysis (FTA), applied to the requirements specification of embedded systems at design time to find out the relationship between individual component failures and overall system failure. FTA helps in determining both qualitative and quantitative relationship between component failures and system failure. Analyzing the system at design time helps in detecting component failures and critical components and helps in devising strategies to mitigate component failures at design time and improve overall safety and reliability of a system.

La problématique de ce doctorat est : comment la structure des réseaux constitue une nouvelle matrice pour la production d’oeuvres artistiques. Pour répondre à cette question, nous commencerons en étudiant l’évolution de la notion de « réseau » de l’antiquité jusqu’à aujourd’hui ; les théories des réseaux concernant leur structure et/ou leur dynamique. Ensuite nous présenterons les applications –de la notion ou des théories de réseaux– tant dans les sciences que dans l’art. Nous listerons et nous analyserons huit types de réseaux et puis nous mentionnerons des oeuvres artistiques qui ont été inspirées par ces types de réseaux et/ou qui utilisent certains (types de) réseaux comme matrice pour leur création. Nous proposerons le projet Lignes Imaginaires, un modèle 3D qui se fonde sur la conception d’un métro de lignes imaginaires, voire de lignes dynamiques et/ou paradoxales qui sont en mouvement, apparaissent/disparaissent, créent de l’infrastructure supplémentaire. L’analyse du métro Lignes Imaginaires dévoile l'importance de la géographie et de la spatialité des réseaux, tandis que leur représentation graphique topologique reste insuffisante pour la représentation précise et pour la compréhension de leur structure (paradoxale). En outre, l’innovation du métro Lignes Imaginaires est que son infrastructure est dynamique et auto-organisée, contrairement aux métros traditionnels où les lignes et leurs itinéraires sont fixes. L’objectif du projet artistique Lignes Imaginaires est de visualiser un concept en créant un métro hors du commun qui pourrait aussi proposer des formes alternatives des réseaux de transports dans le contexte urbain. / This thesis examines and shows ways in which the structure of networks can provide a new matrix for the production of artworks. In order to answer this question we start by studying: the evolution of the term ‘network’ from the ancient times up to nowadays; the theories that refer to network structure or network dynamics. Then we present the applications of these theories into both art and science. We list and analyze eight different types of networks and then we feature artworks which have been inspired by these network types or have used the network structure of a certain type as a matrix for art making. We propose the Imaginary Lines project, a three-dimensional network model which is based on the concept of a metro composed of imaginary lines. More precisely Imaginary Lines metro network encompasses seven paradoxical lines which move, (dis)appear and produce supplementary infrastructure. The Imaginary Lines metro unveils the importance of geography and spatiality, in contrast with topological network graphic representations, which remain insufficient, in terms of utmost accuracy in representation and comprehension of network structure. Additionally, the Imaginary Lines network innovation lays in its infrastructure dynamics as well as in its self-organisation. The objective of the Imaginary Lines artistic project is to visualise a concept by creating an unusual metro, which goes beyond traditional fixed-route transport networks and can support alternative forms of urban transport development.

Many problems in applied mathematics and physics are formulated most naturally in terms of matrices, and can be solved by computing functions of these matrices. For example, in quantum mechanics, the coherent dynamics of physical systems is described by the matrix exponential of their Hamiltonian. In state of the art experiments, one can now observe such unitary evolution of many-body systems, which is of fundamental interest in the study of many-body quantum phenomena. On the other hand the theoretical simulation of such non-equilibrium many-body dynamics is very challenging. In this thesis, we develop a symbolic approach to matrix functions and quantum dynamics based on a novel algebraic structure we identify for sets of walks on graphs. We begin by establishing the graph theoretic equivalent to the fundamental theorem of arithmetic: all the walks on any finite digraph uniquely factorise into products of prime elements. These are the simple paths and simple cycles, walks forbidden from visiting any vertex more than once. We give an algorithm that efficiently factorises individual walks and obtain a recursive formula to factorise sets of walks. This yields a universal continued fraction representation for the formal series of all walks on digraphs. It only involves simple paths and simple cycles and is thus called a path-sum. In the second part, we recast matrix functions into path-sums. We present explicit results for a matrix raised to a complex power, the matrix exponential, matrix inverse, and matrix logarithm. We introduce generalised matrix powers which extend desirable properties of the Drazin inverse to all powers of a matrix. In the third part, we derive an intermediary form of path-sum, called walk-sum, relying solely on physical considerations. Walk-sum describes the dynamics of a quantum system as resulting from the coherent superposition of its histories, a discrete analogue to the Feynman path-integrals. Using walk-sum we simulate the dynamics of quantum random walks and of Rydberg-excited Mott insulators. Using path-sum, we demonstrate many-body Anderson localisation in an interacting disordered spin system. We give two observable signatures of this phenomenon: localisation of the system magnetisation and of the linear magnetic response function. Lastly we return to the study of sets of walks. We show that one can construct as many representations of series of walks as there are ways to define a walk product such that the factorisation of a walk always exist and is unique. Illustrating this result we briefly present three further methods to evaluate functions of matrices. Regardless of the method used, we show that graphs are uniquely characterised, up to an isomorphism, by the prime walks they sustain.