CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015

Applications of graph theory

TOMAS BOOTHBY, Simon Fraser University
Fast clique minor generation in grid-like qubit connectivity graphs.  [PDF]

Qubits in a D-Wave quantum annealing processor have connectivity specified by a grid-like ``Chimera'' graph $C_{m,n,\ell}$. In order to solve an Ising spin problem with arbitrary connectivity, the problem must be minor-embedded into a Chimera graph. We describe a combinatorial class of ``natively structured'' clique minors in Chimera graphs, and use this description to produce a polynomial-time algorithm that finds a maximum natively structured clique minor in a given induced subgraph of Chimera. This problem has immediate applications in the study of quantum annealing.

KRIS VASUDEVAN, University of Calgary
Graph theory applications: Earthquake sequencing, epileptic seizures  [PDF]

Graph theory is extensively used to study the dynamical behavior of complex networks depicting naturally occurring processes such as earthquakes, epileptic seizures and complex cell reactions. Here, we show how we construct the graphs for earthquake and epileptic seizure studies. Then, we present new spectral graph theory measures in the sense of the Laplacian spectrum of directed graphs. We also explore possible relationships between the results of the dynamics of oscillations and the spectral graph properties. Finally, we consider the dynamics of evolving directed graphs in terms of rewiring of vertices at regular intervals.

* Work done with Michael Cavers

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Saskatchewan