Kathie Cameron
Professor
Faculty of Science
Mathematics
Waterloo, Ontario
kcameron@wlu.ca
Office:
(519) 884-0710 ext. 2651
Expert In
Languages
English
Bio/Research
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 >>
Bio/Research
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 <<
Media Relations
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 >>
Media Relations
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 <<