Thesis (M.C.S.)--Carleton University, 1992. / Also available in electronic format on the Internet.

Thesis (M.S.)--Rochester Institute of Technology, 2005. / Typescript. Includes bibliographical references (leaves 89-94).

A morph between two drawings of the same graph can be thought of as a continuous deformation between the two given drawings. A morph is linear if every vertex moves along a straight line segment from its initial position to its final position. In this thesis we study algorithms for morphing, in which the morphs are given by sequences of linear morphing steps. In 1944, Cairns proved that it is possible to morph between any two planar drawings of a planar triangulation while preserving planarity during the morph. However this morph may require exponentially many steps. It was not until 2013 that Alamdari et al. proved that the morphing problem for planar triangulations can be solved using polynomially many steps. In 1990 it was shown by Schnyder that using special drawings that we call Schnyder drawings it is possible to draw a planar graph on a O(n)×O(n) grid, and moreover such drawings can be found in O(n) time (here n denotes the number of vertices of the graph). It still remains unknown whether there is an efficient algorithm for morphing in which all drawings are on a polynomially sized grid. In this thesis we give two different new solutions to the morphing problem for planar triangulations. Our first solution gives a strengthening of the result of Alamdari et al. where each step is a unidirectional morph. This also leads to a simpler proof of their result. Our second morphing algorithm finds a planar morph consisting of O(n²) steps between any two Schnyder drawings while remaining in an O(n)×O(n) grid. However, there are drawings of planar triangulations which are not Schnyder drawings, and for these drawings we show that a unidirectional morph consisting of O(n) steps that ends at a Schnyder drawing can be found. We conclude this work by showing that the basic steps from our morphs can be implemented using a Schnyder wood and weight shifts on the set of interior faces.

Random NP-Complete problems have come under study as an important tool used in the analysis of optimization algorithms and help in our understanding of how to properly address issues of computational intractability. In this thesis, the Number Partition Problem and the Hamiltonian Cycle Problem are taken as representative NP-Complete classes. Numerical evidence is presented for a phase transition in the probability of solution when a modified Lévy-Stable distribution is used in instance creation for each. Numerical evidence is presented that show hard random instances exist near the critical threshold for the Hamiltonian Cycle problem. A choice of order parameter for the Number Partition Problem’s phase transition is also given. Finding Hamiltonian Cycles in Erdös-Rényi random graphs is well known to have almost sure polynomial time algorithms, even near the critical threshold. To the author’s knowledge, the graph ensemble presented is the first candidate, without specific graph structure built in, to generate graphs whose Hamiltonicity is intrinsically hard to determine. Random graphs are chosen via their degree sequence generated from a discretized form of Lévy-Stable distributions. Graphs chosen from this distribution still show a phase transition and appear to have a pickup in search cost for the algorithms considered. Search cost is highly dependent on the particular algorithm used and the graph ensemble is presented only as a potential graph ensemble to generate intrinsically hard graphs that are difficult to test for Hamiltonicity. Number Partition Problem instances are created by choosing each element in the list from a modified Lévy-Stable distribution. The Number Partition Problem has no known good approximation algorithms and so only numerical evidence to show the phase transition is provided without considerable focus on pickup in search cost for the solvers used. The failure of current approximation algorithms and potential candidate approximation algorithms are discussed.

Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. If one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. All such safe walks were recently characterized as omnitigs, leading to the first safe and complete genome assembly algorithm. Even if omnitig finding was improved to quadratic time, it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We describe an O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ(mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig, with two consequences: a linear-time output sensitive algorithm enumerating all maximal omnitigs and a compact O(m) representation of all maximal omnitigs. This safe and complete genome assembly algorithm was followed by other works improving the time bounds, as well as extending the results for different notions of assembly solution. But it remained open whether one can be complete also for models of genome assembly of practical applicability. In this dissertation, we also present a universal framework for obtaining safe and complete algorithms which unify the previous results, while also allowing to characterize different assembly problems. This is based on a novel graph structure, called the hydrostructure of a walk, which highlights the reachability properties of the graph from the perspective of the walk. Almost all of our characterizations are directly adaptable to optimal verification algorithms, and simple enumeration algorithms. Most of these algorithms are also improved to optimality using an incremental computation procedure and a previous optimal algorithm of a specific model.

Thesis (M.C.S.) - Carleton University, 2005. / Includes bibliographical references (p. 127-130). Also available in electronic format on the Internet.