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.
Join us at Laurier
Becoming a Golden Hawk means more than just cheering on our (really good) varsity teams – it means being a student who cares about your community, who works hard in the classroom, and who takes advantage of all the learning opportunities that can happen outside the classroom, too.
-
Connect With Us
-
Show Me the Campus
-
Explore Our Programs
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 been at Wilfrid Laurier University since 1989. I have taught graduate courses at Stanford University, Cornell University, Université Pierre et Marie Curie (Paris 6), and the University of Waterloo. Recently, I spent 4 months in China giving lectures at Shanghai Jiao Tong University, Fudan University, Shanghai University, Soochow University, Nanjing University, Nanjing Normal University, Fuzhou University and Zhejiang Normal University.
My research is in graph algorithms and polytime combinatorial optimization. I use linear programming, network optimization, polyhedral combinatrorics and graph structure to develop efficient algorithms for discrete problems, mainly on graphs.
A vast number of fundamental problems on graphs, such as graph colouring, are NP-complete. This is believed to mean that efficient (that is, polytime) 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 for problems on these graphs which are NP-complete in general.
An existentially polytime (EP) theorem is one which states that something which is easy to recognize once you have it always exists. More formally, an EP theorem is an NP predicate which is always true. Jack Edmonds and I have raised the meta-conjecture that for every EP-theorem, there is a polytime algorithm to find what it asserts to exist. Much of my research focuses on finding such algorithms.
My current projects include finding a second degree-constrained spanning tree, intermediate trees, easily recognizable strong stable sets, rainbow matchings and monotone path systems in polygonal regions.
I am interested in supervising undergraduate and graduate students students in research projects in optimization, graph theory and graph algorithms.
- K. Cameron and J. Edmonds. “Coflow polyhedra.” Discrete Mathematics (1992).
- K. Cameron and J. Edmonds. “The travelling preacher, projection, and a lower bound for the stability number of a graph.” Discrete Optimization (2008).
- K. Cameron, E. Eschen, C. Hoàng, and R. Sritharan. “The complexity of the list partition problem for graphs.” SIAM Journal on Discrete Mathematics (2007).
- K. Cameron and J. Edmonds. “Some graphic uses of an even number of odd nodes.” Annales de l’Institut Fourier (1999).
- K. Cameron. “Thomason’s algorithm for finding a second hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk’s graphs.” Discrete Mathematics (2001).
- K. Cameron, "Induced matchings," Discrete Applied Mathematics (1989), 97-102.
- K. Cameron, “Induced matchings in intersection graphs.” Discrete Mathematics (2004).
- K. Cameron and P. Hell. “Independent packings in structured graphs.” Mathematical Programming Series B (2006).
- K. Cameron and J. Edmonds. “Existentially polytime theorems.” DIMACS (National Science Foundation Science and Technology Centre in Discrete Mathematics and Theoretical Computer Science) Series in Discrete Mathematics and Computer Science Volume 1 (1990).
- K. Cameron, S. Chaplick and C. Hoàng. “Edge-intersection graphs of L-shaped paths in grids.” Discrete Applied Mathematics (2015).
- K. Cameron, S. Chaplick and C. Hoàng. “The structure of (pan, even hole)-free graphs.” (submitted).
Contact Info:
Office location: LH3041
Languages spoken: English