Browsing Combinatorics and Optimization by Title
Now showing items 155-174 of 436
-
Error Bounds and Singularity Degree in Semidefinite Programming
(University of Waterloo, 2020-01-24)An important process in optimization is to determine the quality of a proposed solution. This usually entails calculation of the distance of a proposed solution to the optimal set and is referred to as forward error. ... -
Establishing a Connection Between Graph Structure, Logic, and Language Theory
(University of Waterloo, 2015-09-08)The field of graph structure theory was given life by the Graph Minors Project of Robertson and Seymour, which developed many tools for understanding the way graphs relate to each other and culminated in the proof of the ... -
Evaluating Large Degree Isogenies between Elliptic Curves
(University of Waterloo, 2010-12-20)An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves ... -
Even Cycle and Even Cut Matroids
(University of Waterloo, 2011-05-20)In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes ... -
Even pairs and prism corners in square-free Berge graphs
(Elsevier, 2018-07)Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair. -
Exact, Approximate, and Online Algorithms for Optimization Problems Arising in DVD Assignment
(University of Waterloo, 2009-09-01)Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular ... -
The Existence of Balanced Tournament Designs and Partitioned Balanced Tournament Designs
(University of Waterloo, 2001)A balanced tournament design of order <I>n</I>, BTD(<I>n</I>), defined on a 2<I>n</I>-set<I> V</i>, is an arrangement of the all of the (2<I>n</i>2) distinct unordered pairs of elements of <I>V</I> into an <I>n</I> X ... -
Exponentially Dense Matroids
(University of Waterloo, 2011-12-15)This thesis deals with questions relating to the maximum density of rank-n matroids in a minor-closed class. Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth ... -
Extending Pappus' Theorem
(University of Waterloo, 2017-12-22)Let $M_1$ and $M_2$ be matroids such that $M_2$ arises from $M_1$ by relaxing a circuit-hyperplane. We will prove that if $M_1$ and $M_2$ are both representable over some finite field $GF(q)$, then $M_1$ and $M_2$ have ... -
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. ...