The intent of my master's thesis is two-fold. First, I wanted to present a largescale work for orchestra that showcased the skills and craft I have developed as a composer (and orchestrator) to date. Secondly, since my goal as a composer is to work in Hollywood as a film composer, I wanted my large-scale work to function as a film score, providing the emotional backbone and highlighting action for a major motion picture. In order to achieve this, I needed a film that was both larger-than-life and contained, in my opinion, an easily replaceable score (or no score at all). After considering and viewing several different films of various genres, the 1956 MGM sci-fi classic Forbidden Planet seemed to be the perfect choice.

The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are universal over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.

Classical vertex coloring problems ask for the minimum number of colors needed to color the vertices of a graph, such that adjacent vertices use different colors. Vertex coloring does have quite a few practical applications in communication theory, industry engineering and computer science. Such examples can be found in the book of Hansen and Marcotte. Deciding whether a graph is 3-colorable or not is a well-known NP-complete problem, even for triangle-free graphs. Intuitively, large girth may help reduce the chromatic number. However, in 1959, Erdos used the probabilitic method to prove that for any two positive integers g and k, there exist graphs of girth at least g and chromatic number at least k. Thus, restricting girth alone does not help bound the chromatic number. However, if we forbid certain tree structure in addition to girth restriction, then it is possible to bound the chromatic number. Randerath determined several such tree structures, and conjectured that if a graph is fork-free and triangle-free, then it is 3-colorable, where a fork is a star K1,4 with two branches subdivided once. The main result of this thesis is that Randerath’s conjecture is true for graphs with odd girth at least 7. We also give a proof that Randerath’s conjecture holds for graphs with maximum degree 4.

Graphene nanoribbons, graphene based optical sensors, and grating based plasmonics are explored experimentally. Graphene nanoribbons exhibit highly insulating states that may allow for graphene based digital applications. We investigate the sensitivity of these states to local charged impurities in ultra high vacuum. We look into the possibility of isolating two-dimensional films of H-BN and BSCCO, and test for any interesting phenomena. We also assess graphene*s applicability for optical sensing by implementing a new style of spectral detector. Utilizing surface plasmon excitations nearby a graphene field-effect transistor we are able to produce a detector with wavelength sensitivity and selectivity in the visible range. Finally, we study another plasmonic phenomenon, and observe the resonant enhancement of diffraction into a symmetry-prohibited order in silver gratings.

This thesis concerns the application of mixed-integer programming techniques to solve special classes of network flow problems and stochastic integer programs. We draw tools from complexity and polyhedral theory to analyze these problems and propose improved solution methods. In the first part, we consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are required to take values above a prespecified minimum threshold whenever they are not zero. These problems find applications in management and supply chain models where orders in small quantities are undesirable. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems. In the second part, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of optimizing a linear function on the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem and finds applications in stochastic integer programming. We observe that the complexity of the problem depends on how P and X are specified. For instance, P can be explicitly given by its linear description, or implicitly by an oracle. Similarly, X can be explicitly given as a list of vectors, or implicitly as a face of P. While removing vertices turns to be hard in general, it is tractable for tractable 0-1 polytopes, and compact extended formulations can be obtained. Some extensions to integral polytopes are also presented. The third part is devoted to the integer L-shaped method for two-stage stochastic integer programs. A widely used model assumes that decisions are made in a two-step fashion, where first-stage decisions are followed by second-stage recourse actions after the uncertain parameters are observed, and we seek to minimize the expected overall cost. In the case of finitely many possible outcomes or scenarios, the integer L-shaped method proposes a decomposition scheme akin to Benders' decomposition for linear problems, but where a series of mixed-integer subproblems have to be solved at each iteration. To improve the performance of the method, we devise a simple modification that alternates between linear and mixed-integer subproblems, yielding significant time savings in instances from the literature. We also present a general framework to generate optimality cuts via a cut-generating problem. Using an extended formulation of the forbidden-vertices problem, we recast our cut-generating problem as a linear problem and embed it within the integer L-shaped method. Our numerical experiments suggest that this approach can prove beneficial when the first-stage set is relatively complicated.

<p>An atom or ion can change quantum state, usually through emission or absorption of a photon. The photon has the same energy as the energy difference between the states of the transition. The states, or energy levels, of an atom are quantized and light emitted, or absorbed, from the atom is therefore of specific wavelengths, giving spectral lines. The spectrum of an atomic ion is unique and contains information of the structure and energy levels of the ion. The spectrum of an atom can be used as a fingerprint in determinations of the abundance of the element in different objects.</p><p>This thesis is focused on some weak effects observed by spectroscopy. Although the effects are weak, they turn out to be of great importance. According to quantum mechanics transitions between certain states are not allowed. Here the weak effects open the possibility for transitions. Spectral lines from forbidden transitions are very weak and difficult to observe under ordinary laboratorial conditions, but they are commonly observed from astrophysical objects and can be very useful for diagnostics of astrophysical plasmas. The first reported observation of forbidden lines was from an astrophysical object and at that time supposed to be from new, previous unknown, elements. If all possible decay channels from an energy level are forbidden, the energy level is metastable and has usually a lifetime 10$^8$ times longer than an ordinary excited state. Measurements of such long lifetimes are difficult since the ion need to be confined during the observation time. Confinement of ions can be achieved with a storage device, such as a storage ring or a trap, where the ions are stored without interacting with each other or the surroundings.</p><p>A laser probing technique has been developed at the storage ring CRYRING, for measurements of lifetimes of metastable states. The technique has now been improved for measurement of longer lifetimes. The technique has also been modified to fit when measuring on negative ions. Results of lifetime measurements are reported and the techniques and methods used are described.</p><p>Another weak effect is hyperfine interaction, which splits the energy levels of an atom or ion. Hyperfine splitting is very small and usually special spectral techniques are needed to resolve such structure. A laser can, in combination with an electromagnetic radio-frequency field, be used for accurate determination of hyperfine structures in atomic ions. Such measurements are also important for evaluation of astrophysical properties, since hyperfine structure can broaden the spectral lines. An experimental setup for such double resonance measurements has been developed and constructed. Results of experimental measurements are reported and the technique is described.</p>

Researchers have been investigating the optimal route query problem for a long time. Optimal route queries are categorized as either unconstrained or constrained queries. Many main memory based algorithms have been developed to deal with the optimal route query problem. Among these, Dijkstra's shortest path algorithm is one of the most popular algorithms for the unconstrained route query problem. The constrained route query problem is more complicated than the unconstrained one, and some constrained route query problems such as the Traveling Salesman Problem and Hamiltonian Path Problem are NP-hard. There are many algorithms dealing with the constrained route query problem, but most of them only solve a specific case. In addition, all of them require that the entire graph resides in the main memory. Recently, due to the need of applications in very large graphs, such as the digital maps managed by Geographic Information Systems (GIS), several disk-based algorithms have been derived by using divide-and-conquer techniques to solve the shortest path problem in a very large graph. However, until now little research has been conducted on the disk-based constrained problem. <br /><br /> This thesis presents two algorithms: 1) a new disk-based shortest path algorithm (DiskSPNN), and 2) a new disk-based optimal path algorithm (DiskOP) that answers an optimal route query without passing a set of forbidden edges in a very large graph. Both algorithms fit within the same divide-and-conquer framework as the existing disk-based shortest path algorithms proposed by Ning Zhang and Heechul Lim. Several techniques, including query super graph, successor fragment and open boundary node pruning are proposed to improve the performance of the previous disk-based shortest path algorithms. Furthermore, these techniques are applied to the DiskOP algorithm with minor changes. The proposed DiskOP algorithm depends on the concept of collecting a set of boundary vertices and simultaneously relaxing their adjacent super edges. Even if the forbidden edges are distributed in all the fragments of a graph, the DiskOP algorithm requires little memory. Our experimental results indicate that the DiskSPNN algorithm performs better than the original ones with respect to the I/O cost as well as the running time, and the DiskOP algorithm successfully solves a specific constrained route query problem in a very large graph.

Cette recherche propose une réflexion sur les enjeux que recouvre la pédophilie dans la société occidentale contemporaine. Dans le premier chapitre, il sera d’abord question d’autorité : afin de bien comprendre le rapport entretenu avec l’autorité et l’importance accordée au système hiérarchique dans la société occidentale contemporaine, nous établirons une comparaison avec les sociétés grecques puisque celles-ci ont accepté et valorisé les relations intergénérationnelles. C’est à travers une lecture de différents textes de Michel Foucault et de Kenneth James Dover que nous approfondirons ces rapports. Cette première partie sera essentielle en ce qu’elle nous aidera à comprendre la façon dont les bases de la société occidentale contemporaine ont été édifiées, l’importance de la catégorisation des genres et les raisons du rejet des relations pédophiliques aujourd’hui. Dans le second chapitre, nous analyserons plus spécifiquement deux œuvres littéraires, La Mort à Venise de Thomas Mann et Quand mourut Jonathan de Tony Duvert, afin de percevoir le malaise que provoque la pédophilie. C’est notamment à travers une étude des figures sociales et de l’éducation que nous tenterons de saisir la place attribuée à la pédophilie. Cette étude se terminera par une réflexion autour de la photographie et du cinéma, afin de souligner l’impact apporté par le réalisme de ces arts. Nous aborderons ici des œuvres non pornographiques qui exposent des sexualités existantes mais non reconnues. Les différents aspects abordés nous permettront non seulement de saisir l’embarras que suscite la pédophilie, mais également de capter la place qu’on y accorde, ou non, au sein de la société contemporaine. / This research proposes a reflection on the stakes of pedophilia in contemporary western society. In the first chapter, we will raise the question of authority: in order to understand the relation with authority and the importance of a hierarchic system in the contemporary western society, we will compare it with the Greek society which accepted and valued intergenerational relationships. It is especially through a reading of various texts from Michel Foucault and Kenneth James Dover that this study will be conducted. This first part is necessary to understand how the bases of contemporary western society were established, the importance of genders’ categorization and the reason behind the rejection of pedophilia today. In the second chapter, we will more specifically analyze two novels, Thomas Mann’s La Mort à Venise and Tony Duvert’s Quand mourut Jonathan. It is mainly through a study of social figures and education that we will be able to understand the place given to pedophilia. This study will close in a reflection about photography and cinema in order to emphasize the impact of these arts’ realism. We will therefore approach non-pornographic works of art that present existing but never recognized sexualities. These different aspects will enable us to fully understand the embarrassment provoked by pedophilia today, but also to recognize the place it is given, or not, within contemporary society.

An atom or ion can change quantum state, usually through emission or absorption of a photon. The photon has the same energy as the energy difference between the states of the transition. The states, or energy levels, of an atom are quantized and light emitted, or absorbed, from the atom is therefore of specific wavelengths, giving spectral lines. The spectrum of an atomic ion is unique and contains information of the structure and energy levels of the ion. The spectrum of an atom can be used as a fingerprint in determinations of the abundance of the element in different objects. This thesis is focused on some weak effects observed by spectroscopy. Although the effects are weak, they turn out to be of great importance. According to quantum mechanics transitions between certain states are not allowed. Here the weak effects open the possibility for transitions. Spectral lines from forbidden transitions are very weak and difficult to observe under ordinary laboratorial conditions, but they are commonly observed from astrophysical objects and can be very useful for diagnostics of astrophysical plasmas. The first reported observation of forbidden lines was from an astrophysical object and at that time supposed to be from new, previous unknown, elements. If all possible decay channels from an energy level are forbidden, the energy level is metastable and has usually a lifetime 10$^8$ times longer than an ordinary excited state. Measurements of such long lifetimes are difficult since the ion need to be confined during the observation time. Confinement of ions can be achieved with a storage device, such as a storage ring or a trap, where the ions are stored without interacting with each other or the surroundings. A laser probing technique has been developed at the storage ring CRYRING, for measurements of lifetimes of metastable states. The technique has now been improved for measurement of longer lifetimes. The technique has also been modified to fit when measuring on negative ions. Results of lifetime measurements are reported and the techniques and methods used are described. Another weak effect is hyperfine interaction, which splits the energy levels of an atom or ion. Hyperfine splitting is very small and usually special spectral techniques are needed to resolve such structure. A laser can, in combination with an electromagnetic radio-frequency field, be used for accurate determination of hyperfine structures in atomic ions. Such measurements are also important for evaluation of astrophysical properties, since hyperfine structure can broaden the spectral lines. An experimental setup for such double resonance measurements has been developed and constructed. Results of experimental measurements are reported and the technique is described.

Finding a shortest path is one of the most well-studied optimization problems. In this thesis we focus on shortest paths in geometric and graph theoretic settings subject to different feasibility constraints that arise in practical applications of such paths. One of the most fundamental problems in computational geometry is finding shortest paths in terrains, which has many applications in robotics, computer graphics and Geographic Information Systems (GISs). There are many variants of the problem in which the feasibility of a path is determined by some geometric property of the terrain. One such variant is the shortest descending path (SDP) problem, where the feasible paths are those that always go downhill. We need to compute an SDP, for example, for laying a canal of minimum length from the source of water at the top of a mountain to fields for irrigation purpose, and for skiing down a mountain along a shortest route. The complexity of finding SDPs is open. We give a full characterization of the bend angles of an SDP, showing that they follow a generalized form of Snell's law of refraction of light. We also reduce the SDP problem to the problem of finding an SDP through a given sequence of faces, by adapting the sequence tree approach of Chen and Han for our problem. Our results have two implications. First, we isolate the difficult aspect of SDPs. The difficulty is not in deciding which face sequence to use, but in finding the SDP through a given face sequence. Secondly, our results help us identify some classes of terrains for which the SDP problem is solvable in polynomial time. We give algorithms for two such classes. The difficulty of finding an exact SDP motivates the study of approximation algorithms for the problem. We devise two approximation algorithms for SDPs in general terrains---these are the first two algorithms to handle the SDP problem in such terrains. The algorithms are robust and easy-to-implement. We also give two approximation algorithms for the case when a face sequence is given. The first one solves the problem by formulating it as a convex optimization problem. The second one uses binary search together with our characterization of the bend angles of an SDP to locate an approximate path. We introduce a generalization of the SDP problem, called the shortest gently descending path (SGDP) problem, where a path descends but not too steeply. The additional constraint to disallow a very steep descent makes the paths more realistic in practice. For example, a vehicle cannot follow a too steep descent---this is why a mountain road has hairpin bends. We give two easy-to-implement approximation algorithms for SGDPs, both using the Steiner point approach. Between a pair of points there can be many SGDPs with different number of bends. In practice an SGDP with fewer bends or smaller total turn-angle is preferred. We show using a reduction from 3-SAT that finding an SGDP with a limited number of bends or a limited total turn-angle is hard. The hardness result applies to a generalization of the SGDP problem called the shortest anisotropic path problem, which is a well-studied computational geometry problem with many practical applications (e.g., robot motion planning), yet of unknown complexity. Besides geometric shortest paths, we also study a variant of the shortest path problem in graphs: given a weighted graph G and vertices s and t, and given a set X of forbidden paths in G, find a shortest s-t path P such that no path in X is a subpath of P. Path P is allowed to repeat vertices and edges. We call each path in X an exception, and our desired path a shortest exception avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception x in X only when a path containing x fails. This situation arises in computing shortest paths in optical networks. We give an easy-to-implement algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The algorithm handles a forbidden path using vertex replication, i.e., replicating vertices and judiciously deleting edges so as to remove the forbidden path but keep all of its subpaths. The main challenge is that vertex replication can result in an exponential number of copies of any forbidden path that overlaps the current one. The algorithm couples vertex replication with the "growth" of a shortest path tree in such a way that the extra copies of forbidden paths produced during vertex replication are immaterial.