Browsing Combinatorics and Optimization by Title
Now showing items 164-183 of 436
-
Extensions of Galvin's Theorem
(University of Waterloo, 2018-04-30)We discuss problems in list coloring with an emphasis on techniques that utilize oriented graphs. Our central theme is Galvin's resolution of the Dinitz problem (Galvin. J. Comb. Theory, Ser. B 63(1), 1995, 153--158). We ... -
Extensions of Signed Graphs
(University of Waterloo, 2014-04-29)Given a signed graph (G, Σ) with an embedding on a surface S, we are interested in "extending" (G, Σ) by adding edges and splitting vertices, such that the resulting graph has no embedding on S. We show (assuming 3-connectivity ... -
FACES OF MATCHING POLYHEDRA
(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
(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
(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
(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
(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
(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
(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
(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
(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 ...