Browsing Combinatorics and Optimization by Title
Now showing items 215-234 of 434
-
Lattice Paths
(University of Waterloo, 2022-08-24)This thesis is a survey of some of the well known results in lattice path theory. Chapter 1 looks into the history of lattice paths. That is, when it began and how it was popularized. Chapter 3 focuses on general lattices ... -
Learning Quantum States Without Entangled Measurements
(University of Waterloo, 2021-10-22)How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at ... -
A Linear Algebraic Method on the Chromatic Symmetric Function
(University of Waterloo, 2023-08-28)The Stanley-Stembridge conjecture is a longstanding conjecture that has evaded proof for nearly 30 years. Concerned with the e-basis expansions of the chromatic symmetric functions of unit-interval graphs, this conjecture ... -
Linear Programming Tools and Approximation Algorithms for Combinatorial Optimization
(University of Waterloo, 2010-01-05)We study techniques, approximation algorithms, structural properties and lower bounds related to applications of linear programs in combinatorial optimization. The following "Steiner tree problem" is central: given a graph ... -
Linearly-dense classes of matroids with bounded branch-width
(University of Waterloo, 2017-09-27)Let $M$ be a non-empty minor-closed class of matroids with bounded branch-width that does not contain arbitrarily large simple rank-$2$ matroids. For each non-negative integer $n$ we denote by $ex(n)$ the size of the ... -
The Linkage Problem for Group-labelled Graphs
(University of Waterloo, 2009-09-24)This thesis aims to extend some of the results of the Graph Minors Project of Robertson and Seymour to "group-labelled graphs". Let $\Gamma$ be a group. A $\Gamma$-labelled graph is an oriented graph with its edges labelled ... -
List 3-Coloring Graphs with No Induced P6+rP3
(Springer Nature, 2021-01-01)For an integer t, we let Pt denote the t-vertex path. We write H+G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph ... -
List 3-coloring Pt-free graphs with no induced 1-subdivision of K1,s
(Elsevier, 2020-11)Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing ... -
List colouring hypergraphs and extremal results for acyclic graphs
(University of Waterloo, 2008-05-21)We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the ... -
The Local Chromatic Number
(University of Waterloo, 2014-01-23)A graph vertex colouring is called k-local if the number of colours used in the closed neighbourhood of each vertex is at most k. The local chromatic number of a graph is the smallest k for which the graph has a proper ... -
Local Perspectives on Planar Colouring
(University of Waterloo, 2022-08-09)In 1994, Thomassen famously proved that every planar graph is 5-choosable, resolving a conjecture initially posed by Vizing and, independently, Erdos, Rubin, and Taylor in the 1970s. Later, Thomassen proved that every ... -
Local properties of graphs with large chromatic number
(University of Waterloo, 2022-08-31)This thesis deals with problems concerning the local properties of graphs with large chromatic number in hereditary classes of graphs. We construct intersection graphs of axis-aligned boxes and of lines in $\mathbb{R}^3$ ... -
Local Structure for Vertex-Minors
(University of Waterloo, 2021-10-12)This thesis is about a conjecture of Geelen on the structure of graphs with a forbidden vertex-minor; the conjecture is like the Graph Minors Structure Theorem of Robertson and Seymour but for vertex-minors instead of ... -
Low-Rank Plus Sparse Decompositions of Large-Scale Matrices via Semidefinite Optimization
(University of Waterloo, 2023-05-19)We study the problem of decomposing a symmetric matrix into the sum of a low-rank symmetric positive semidefinite matrix and a tridiagonal matrix, and a relaxation which looks for symmetric positive semidefinite matrices ... -
LP-based Approximation Algorithms for the Capacitated Facility Location Problem
(University of Waterloo, 2012-05-18)The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a ... -
MAC Constructions: Security Bounds and Distinguishing Attacks
(University of Waterloo, 2007-05-18)We provide a simple and improved security analysis of PMAC, a Parallelizable MAC (Message Authentication Code) defined over arbitrary messages. A similar kind of result was shown by Bellare, Pietrzak and Rogaway at ... -
Machine-Level Software Optimization of Cryptographic Protocols
(University of Waterloo, 2014-04-30)This work explores two methods for practical cryptography on mobile devices. The first method is a quantum-resistant key-exchange protocol proposed by Jao et al.. As the use of mobile devices increases, the deployment of ... -
MacLane's Theorem for Graph-Like Spaces
(University of Waterloo, 2008-09-12)The cycle space of a finite graph is the subspace of the edge space generated by the edge sets of cycles, and is a well-studied object in graph theory. Recently progress has been made towards extending the theory of cycle ... -
The Master Equality Polyhedron: Two-Slope Facets and Separation Algorithm
(University of Waterloo, 2015-08-11)This thesis presents our findings about the Master Equality Polyhedron (MEP), an extension of Gomory's Master Group Polyhedron. We prove a theorem analogous to Gomory and Johnson's two-slope theorem for the case of the ... -
The Matching Augmentation Problem: A 7/4-Approximation Algorithm
(University of Waterloo, 2019-05-23)We present a 7/4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected ...