I am interested in algorithms, especially algorithmic graph theory. Much of my work relates to classes of graphs for which certain NP-hard optimization problems (e.g. min colour, max clique, max independent set) can be solved in polynomial time. Some such graph classes (e.g. weakly chordal graphs) are sufficiently general to include many well known classes of graphs, and/or many classes of graphs which arise from various applications.
I am also interested in algorithms for 2-player board games, especially Hex.
- Algorithms for Hex players and solvers (with P. Henderson and B. Arneson)
- Integer programming feasibility heuristics (with S. Ghosh)
- Weakly chordal graph optimization and recognition (with J. Spinrad and R. Sritharan)