Browsing Combinatorics and Optimization by Type "Doctoral Thesis"
Now showing items 21-40 of 122
-
Computing with Multi-Row Intersection Cuts
(University of Waterloo, 2017-05-16)Cutting planes are one of the main techniques currently used to solve large-scale Mixed-Integer Linear Programming (MIP) models. Many important cuts used in practice, such as Gomory Mixed-Integer (GMI) cuts, are obtained ... -
Connectivity, tree-decompositions and unavoidable-minors
(University of Waterloo, 2015-05-06)The results in this thesis are steps toward bridging the gap between the handful of exact structure theorems known for minor-closed classes of graphs, and the very general, yet wildly qualitative, Graph Minors Structure ... -
Constructing Cospectral and Comatching Graphs
(University of Waterloo, 2019-07-18)The matching polynomial is a graph polynomial that does not only have interesting mathematical properties, but also possesses meaningful applications in physics and chemistry. For a simple graph, the matching polynomial ... -
Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems
(University of Waterloo, 2021-08-23)The objective of a combinatorial optimization problem is to find an element that maximizes a given function defined over a large and possibly high-dimensional finite set. It is often the case that the set is so large that ... -
Convex Optimization via Domain-Driven Barriers and Primal-Dual Interior-Point Methods
(University of Waterloo, 2017-08-24)This thesis studies the theory and implementation of infeasible-start primal-dual interior-point methods for convex optimization problems. Convex optimization has applications in many fields of engineering and science such ... -
Convex relaxation for the planted clique, biclique, and clustering problems
(University of Waterloo, 2011-08-24)A clique of a graph G is a set of pairwise adjacent nodes of G. Similarly, a biclique (U, V ) of a bipartite graph G is a pair of disjoint, independent vertex sets such that each node in U is adjacent to every node in V ... -
Core Structures in Random Graphs and Hypergraphs
(University of Waterloo, 2013-08-30)The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by Bollobás in 1984 in connection to k-connected subgraphs of random graphs. Subsequently, ... -
Counting Bases
(University of Waterloo, 2004)A theorem of Edmonds characterizes when a pair of matroids has a common basis. Enumerating the common bases of a pair of matroid is a much harder problem, and includes the #P-complete problem of counting the number of ... -
Design, Analysis, and Optimization of Isogeny-Based Key Establishment Protocols
(University of Waterloo, 2020-08-19)We analyze the Commutative Supersingular Isogeny Diffie-Hellman protocol (CSIDH), a novel supersingular isogeny-based key establishment protocol. Our analysis is from three perspectives: Quantum Cryptanalysis. Building ... -
Diameter and Rumour Spreading in Real-World Network Models
(University of Waterloo, 2015-04-20)The so-called 'small-world phenomenon', observed in many real-world networks, is that there is a short path between any two nodes of a network, whose length is much smaller that the network's size, typically growing as a ... -
Differential Equations and Depth First Search for Enumeration of Maps in Surfaces
(University of Waterloo, 1999)A map is an embedding of the vertices and edges of a graph into a compact 2-manifold such that the remainder of the surface has components homeomorphic to open disks. With the goal of proving the Four Colour Theorem, ... -
Disasters in Abstracting Combinatorial Properties of Linear Dependence
(University of Waterloo, 2020-05-15)A notion of geometric structure can be given to a set of points without using a coordinate system by instead describing geometric relations between finite combinations of elements. The fundamental problem is to then ... -
Discrete Logarithm Cryptography
(University of Waterloo, 2010-04-27)The security of many cryptographic schemes relies on the intractability of the discrete logarithm problem (DLP) in groups. The most commonly used groups to deploy such schemes are the multiplicative (sub)groups of finite ... -
Discrete Quantum Walks on Graphs and Digraphs
(University of Waterloo, 2018-09-26)This thesis studies various models of discrete quantum walks on graphs and digraphs via a spectral approach. A discrete quantum walk on a digraph $X$ is determined by a unitary matrix $U$, which acts on complex functions ... -
Distance-Biregular Graphs and Orthogonal Polynomials
(University of Waterloo, 2023-09-15)This thesis is about distance-biregular graphs– when they exist, what algebraic and structural properties they have, and how they arise in extremal problems. We develop a set of necessary conditions for a distance-biregular ... -
Edge-disjoint Linkages in Infinite Graphs
(University of Waterloo, 2022-09-26)The main subject of this thesis is the infinite graph version of the weak linkage conjecture by Thomassen [24]. We first prove results about the structure of the lifting graph; Theorems 2.2.8, 2.2.24, and 2.3.1. As an ... -
Efficient Integer Representations for Cryptographic Operations
(University of Waterloo, 2004)Every positive integer has a unique radix 2 representation which uses the digits {0,1}. However, if we allow digits other than 0 and 1, say {0,1,-1}, then a positive integer has many representations. Of these ... -
Enumerating matroid extensions
(University of Waterloo, 2023-09-01)This thesis investigates the problem of enumerating the extensions of certain matroids. A matroid M is an extension of a matroid N if M delete e is equal to N for some element e of M. Similarly, a matroid M is a coextension ... -
Enumeration of Factorizations in the Symmetric Group: From Centrality to Non-centrality
(University of Waterloo, 2011-04-25)The character theory of the symmetric group is a powerful method of studying enu- merative questions about factorizations of permutations, which arise in areas including topology, geometry, and mathematical physics. This ... -
Enumerative Applications of Integrable Hierarchies
(University of Waterloo, 2015-05-21)Countably infinite families of partial differential equations such as the Kadomtzev - Petviashvili (KP) hierarchy and the B-type KP (BKP) hierarchy have received much interest in the mathematical and theoretical physics ...