Professor
Faculty of Science
Mathematics
Waterloo, Ontario
kcameron@wlu.ca
Office:
(519) 884-0710 ext. 2651

English

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), Unive...

Click to Expand >>

I have taught graduate courses at Stanford University, Cornell University, Université Pierre et Marie Curie (Paris 6), Unive...

Click to Expand >>

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.

Click to Shrink <<

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.

Click to Shrink <<

Aonghus Kealy

Communications and Media Relations Officer

akealy@wlu.ca

(548) 889-4855

Click to Expand >>

Communications and Media Relations Officer

akealy@wlu.ca

(548) 889-4855

Click to Expand >>

Aonghus Kealy

Communications and Media Relations Officer

akealy@wlu.ca

(548) 889-4855

Lori Chalmers Morrison

Director: Integrated Communications

lchalmersmorrison@wlu.ca

(548) 889-4857

Vanessa Barrasa

Director: Communications & Issues Management

vbarrasa@wlu.ca

(548) 889-3812

Brantford Campus:

Beth Gurney

Director, Strategic Communications and Community Engagement

bgurney@wlu.ca

(548) 889-4199

Click to Shrink <<

Communications and Media Relations Officer

akealy@wlu.ca

(548) 889-4855

Lori Chalmers Morrison

Director: Integrated Communications

lchalmersmorrison@wlu.ca

(548) 889-4857

Vanessa Barrasa

Director: Communications & Issues Management

vbarrasa@wlu.ca

(548) 889-3812

Brantford Campus:

Beth Gurney

Director, Strategic Communications and Community Engagement

bgurney@wlu.ca

(548) 889-4199

Click to Shrink <<