Now showing items 164-183 of 433

    • FACES OF MATCHING POLYHEDRA 

      Pulleyblank, William R. (University of Waterloo, 2016-09-30)
      Let G = (V, E, ~) be a finite loopless graph, let b=(bi:ieV) be a vector of positive integers. A feasible matching is a vector X = (x.: j e: E) J of nonnegative integers such that for each node i of G, the sum of ...
    • Fast Bootstrapping in Z_q 

      Ruiz Lopez, Luis A (University of Waterloo, 2015-08-28)
      In 2015, Ducas and Micciancio presented a novel technique to compute the NAND gate using the Learning With Errors cryptosystem (LWE), along with a novel bootstrapping technique that turns turns this cryptosystem into a ...
    • Fast Prefix Adders for Non-uniform Input Arrival Times 

      Held, Stephan; Spirkl, Sophie (Springer Nature, 2017)
      We consider the problem of constructing fast and small parallel prefix adders for non-uniform input arrival times. In modern computer chips, adders with up to hundreds of inputs occur frequently, and they are often embedded ...
    • Finding a Second Hamiltonian cycle in Barnette Graphs 

      Haddadan, Arash (University of Waterloo, 2015-08-31)
      We study the following two problems: (1) finding a second room-partitioning of an oik, and (2) finding a second Hamiltonian cycle in cubic graphs. The existence of solution for both problems is guaranteed by a parity ...
    • Finding an induced path that is not a shortest path 

      Berger, Eli; Seymour, Paul; Spirkl, Sophie (Elsevier, 2021-07)
      We give a polynomial-time algorithm that, with input a graph G and two vertices u; v of G, decides whether there is an induced uv-path that is longer than the shortest uv-path.
    • Finding Independent Transversals Efficiently 

      Graf, Alessandra (University of Waterloo, 2019-08-23)
      Let G be a graph and (V_1,...,V_m) be a vertex partition of G. An independent transversal (IT) of G with respect to (V_1,...,V_m) is an independent set {v_1,...,v_m} in G such that v_i is in V_i for each i in {1,...,m}. There ...
    • Finding Large H-Colorable Subgraphs in Hereditary Graph Classes 

      Chudnovsky, Maria; King, Jason; Pilipczuk, Michał; Rzążewski, Paweł; Spirkl, Sophie (Society for Industrial and Applied Mathematics, 2021-10-14)
      We study the Max Partial H-Coloring problem: given a graph G, find the largest induced subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without loops. Note that when H is a complete graph ...
    • Formalizing the Excluded Minor Characterization of Binary Matroids in the Lean Theorem Prover 

      Gusakov, Alena (University of Waterloo, 2024-01-23)
      A matroid is a mathematical object that generalizes the notion of linear independence of a set of vectors to an abstract independence of sets, with applications to optimization, linear algebra, graph theory, and algebraic ...
    • Four-coloring P6-free graphs 

      Chudnovsky, Maria; Spirkl, Sophie; Zhong, Mingxian (Association for Computing Machinery, 2019)
      In this paper we present a polynomial time algorithm for the 4-COLORING PROBLEM and the 4-PRECOLORING EXTENSION problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. ...
    • Fractional refinements of integral theorems 

      Moore, Benjamin (University of Waterloo, 2021-07-09)
      The focus of this thesis is to take theorems which deal with ``integral" objects in graph theory and consider fractional refinements of them to gain additional structure. A classic theorem of Hakimi says that for an ...
    • A Fundamentally Topological Perspective on Graph Theory 

      Vella, Antoine (University of Waterloo, 2005)
      We adopt a novel topological approach for graphs, in which edges are modelled as points as opposed to arcs. The model of classical <i>topologized graphs</i> translates graph isomorphism into topological homeomorphism, ...
    • A Generalization to Signed Graphs of a Theorem of Sergey Norin and Robin Thomas 

      Horrocks, Courtney (University of Waterloo, 2019-12-19)
      In this thesis we characterize the minimal non-planar extensions of a signed graph. We consider the following question: Given a subdivision of a planar signed graph (G, Σ), what are the minimal structures that can be added ...
    • Generating Functions for Hyperbolic Plane Tessellations 

      Xie, Jiale (University of Waterloo, 2017-08-28)
      For a hyperbolic plane tessellation there is a generating function with respect to the distance. This generating function is the same as the growth function of a group of isometries of hyperbolic plane that acts regularly ...
    • Generation and properties of random graphs and analysis of randomized algorithms 

      Gao, Pu (University of Waterloo, 2010-01-22)
      We study a new method of generating random $d$-regular graphs by repeatedly applying an operation called pegging. The pegging algorithm, which applies the pegging operation in each step, is a method of generating large ...
    • Genus one partitions 

      Yip, Martha (University of Waterloo, 2006)
      We obtain a tight upper bound for the genus of a partition, and calculate the number of partitions of maximal genus. The generating series for genus zero and genus one rooted hypermonopoles is obtained in closed form ...
    • Geometric Ramifications of the Lovász Theta Function and Their Interplay with Duality 

      de Carli Silva, Marcel Kenji (University of Waterloo, 2013-08-30)
      The Lovasz theta function and the associated convex sets known as theta bodies are fundamental objects in combinatorial and semidefinite optimization. They are accompanied by a rich duality theory and deep connections ...
    • Geometry of convex sets arising from hyperbolic polynomials 

      Myklebust, Tor Gunnar Josefsson Jay (University of Waterloo, 2008-09-09)
      This thesis focuses on convex sets and convex cones defined using hyperbolic polynomials. We first review some of the theory of convex sets in $\R^d$ in general. We then review some classical algebraic theorems concerning ...
    • Goldberg's conjecture is true for random multigraphs 

      Haxell, Penny; Krivelevich, Michael; Kronenberg, Gal (Elsevier, 2019-09)
      In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph G, the chromatic index χ′(G) satisfies χ′(G) ≤ max{∆(G)+1,⌈ρ(G)⌉}, where ρ(G) = max\{\frac {e(G[S])}{\lfloor|S|/2\rfloor} \mid S\subseteq ...
    • Graph Coverings with Few Eigenvalues or No Short Cycles 

      Levit, Maxwell (University of Waterloo, 2023-05-18)
      This thesis addresses the extent of the covering graph construction. How much must a cover X resemble the graph Y that it covers? How much can X deviate from Y? The main statistics of X and Y which we will measure are their ...
    • Graph-Theoretic Techniques for Optimizing NISQ Algorithms 

      Jena, Andrew (University of Waterloo, 2024-02-15)
      Entering the NISQ era, the search for useful yet simple quantum algorithms is perhaps of more importance now than it may ever be in the future. In place of quantum walks, the quantum Fourier transform, and asymptotic results ...

      UWSpace

      University of Waterloo Library
      200 University Avenue West
      Waterloo, Ontario, Canada N2L 3G1
      519 888 4883

      All items in UWSpace are protected by copyright, with all rights reserved.

      DSpace software

      Service outages