Browsing Combinatorics and Optimization by Title
Now showing items 174-193 of 436
-
Four-coloring P6-free graphs
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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 ... -
Graphical CSS Code Transformation Using ZX Calculus
(University of Waterloo, 2023-12-21)In this work, we present a generic approach to transform CSS codes by building upon their equivalence to phase-free ZX diagrams. Using the ZX calculus, we demonstrate diagrammatic transformations between encoding maps ... -
The Graphs of HU+00E4ggkvist & Hell
(University of Waterloo, 2009-01-19)This thesis investigates HU+00E4ggkvist & Hell graphs. These graphs are an extension of the idea of Kneser graphs, and as such share many attributes with them. A variety of original results on many different properties of ... -
H-colouring Pt-free graphs in subexponential time
(Elsevier, 2019-08-31)A graph is called Pt-free if it does not contain the path on t vertices as an induced subgraph. Let H be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the ... -
Hamilton Paths in Generalized Petersen Graphs
(University of Waterloo, 2002)This thesis puts forward the conjecture that for <i>n</i> > 3<i>k</i> with <i>k</i> > 2, the generalized Petersen graph, <i>GP</i>(<i>n,k</i>) is Hamilton-laceable if <i>n</i> is even and <i>k</i> is odd, and it is ... -
Hardness results and approximation algorithms for some problems on graphs
(University of Waterloo, 2008-12-17)This thesis has two parts. In the first part, we study some graph covering problems with a non-local covering rule that allows a "remote" node to be covered by repeatedly applying the covering rule. In the second part, we ... -
Highly Non-Convex Crossing Sequences
(University of Waterloo, 2012-05-18)For a given graph, G, the crossing number crₐ(G) denotes the minimum number of edge crossings when a graph is drawn on an orientable surface of genus a. The sequence cr₀(G), cr₁(G), ... is said to be the crossing sequence ... -
Homomorphic Encryption
(University of Waterloo, 2013-01-24)In this thesis, we provide a summary of fully homomorphic encryption, and in particular, look at the BGV encryption scheme by Brakerski, Gentry, and Vaikuntanathan; as well the DGHV encryption scheme by van Dijk, Gentry, ... -
Hurwitz Trees and Tropical Geometry
(University of Waterloo, 2016-01-21)The lifting problem in algebraic geometry asks when a finite group G acting on a curve defined over characteristic p > 0 lifts to characteristic 0. One object used in the study of this problem is the Hurwitz tree, which ...