We use cookies on this site to enhance your experience.
By selecting “Accept” and continuing to use this website, you consent to the use of cookies.
Search for academic programs, residence, tours and events and more.
I received my masters and PhD in Combinatorics and Optimization at the University of Waterloo following a BSc (Honours) in Mathematics at the University of Regina.
I have taught graduate courses at Stanford University, Cornell University, Université Pierre et Marie Curie (Paris 6), University of Waterloo, and here at Laurier. I have made extended research visits in France, Denmark, China, and the U.K.
My research is in graph theory and algorithms.
A vast number of fundamental problems on graphs, such as graph colouring, are NP-complete. This is believed to mean that efficient (that is, polynomial-time) algorithms can not be found for all instances. Often graphs arising in applications have special structure which can be analyzed and exploited to design efficient algorithms on these graphs for problems which are NP-complete in general.
Another main area of my research is on parity theorems. Often parity theorems are proved by counting arguments. Another approach, introduced by Andrew Thomason, is to construct a graph, which we call an exchange graph, in which the odd-degree vertices correspond precisely to the objects one wants to show there are an even number of. Christos Papadimitriou calls this approach the polynomial parity argument (PPA). It provides an algorithm for given one of the objects, finding another, by walking in the exchange graph from one odd-degree vertex to another. A main question is: what is the complexity of such algorithms? Exchange graphs are generally very large compared to the input problem.
My current projects include parity theorems about paths, trees and cycles in graphs, reconfiguration problems on graphs, and degree-constrained spanning trees.
Wilfrid Laurier University, Board of Governors Excellence in Service and Engagement Award, 2023
I am interested in supervising graduate students students and post-docs in research projects in graph structure and algorithms, and in supervising undergraduate students in these and other areas of discrete mathematics.
Contact Info:
Office location: LH3041
Languages spoken: English