Richard Krueger, Ph.D.                             SSH    Instructor Office:   BA 4261 Phone:   416-946-8869 Fax:   416-978-1931 Email:   WWW: http://www.cs.toronto.edu/~krueger Section Links:   About Research Courses Service Personal

Research topics:

I am presently working in Applied Discrete Mathematics / Graph Theory looking at properties of and algorithms for various kinds of grpah search (graph traversals, including BFS and DFS), and their application to creating simple algorithms to solve problems in assorted graph classes.

Unified view of graph search: I am currently working on a project to unify the paradigm of graph search (graph traversal) algorithms. I have found simple characterizations of several types of graph search, and this presents a very interesting insight into what a graph search is and how different searches relate to each other. I use these ideas to devise simple proofs of assorted structural properties.

Graph search and minimal triangulation, separation: Maximal neighborhood searches (MNS) and their extensions exhibit interesting properties, being able to find minimal separators and construct minimal triangulations of nonchordal graphs. There are interesting connections to treewidth/bandwidth and behavior on tree decompositions. One goal is extension of known minimal triangulation ideas from LexBFS to the more general MNS, and further understanding the links MNS reveals to related areas.

Other interests: I am also interested in graph isomorphism, and particularly simple approaches and related questions for planar graphs. I am motivated by simple algorithms for answering questions on graphs, whether it is simplicity in algorithm implementation, simplicity in understanding or teaching the algorithm, simplicity in running the algorithm, or simplicity and beauty in how the algorithm approaches the problem.

Research links:

• Combinatorics Seminar
• Theory Student Seminar
• CS/Math seminars: this week, this month
• Fields Institute
• Forthcoming discrete math conferences

• Citeseer ResearchIndex
• MathSciNet
• MathematicsWeb
• DBLP - Computer Science Bibliography
• The Collection of Computer Science Bibliographies (local mirror)
• FTP site of bibtex format journal bibliographies
• The Graph Theory White Pages
• UofT Library
  • my.library
  • my.utoronto.ca
  • ROSI
• SIAM Journals - topmatter from 1994, fulltext from 1997
• ACM Digital Library
• TeX FAQ

Publications:

Some are hyperlinked: download at your leisure. Those not hyperlinked are available via email (I probably just haven't got around to putting them online yet, or perhaps there are copyright restrictions).

1. A. Berry, R. Krueger and G. Simonet. Maximal Label Search algorithms to compute perfect and minimal elimination orderings. SIAM J. on Discrete Math, in press.
2. Richard Krueger, Genevieve Simonet, Anne Berry. A General Label Search to investigate classical graph search algorithms. Manuscript, submitted.
3. Richard Krueger, Genevieve Simonet. An algorithmic perspective of graph searching. Manuscript, submitted, 2005.
4. Derek G. Corneil and Richard Krueger. Simple vertex ordering characterizations for graph search. In Proceedings of 7th International Colloquium on Graph Theory (ICGT '05), September 2005. Electronic Notes in Discrete Mathematics 22 (2005), 445-449.
5. A. Berry, J. Blair, J.-P. Bordat, R. Krueger and G. Simonet. Extremities and orderings defined by generalized graph search algorithms. In Proceedings of 7th International Colloquium on Graph Theory (ICGT '05), September 2005. Electronic Notes in Discrete Mathematics 22 (2005), 413-420.
6. Richard Krueger. Graph Searching. Ph.D. Thesis, Department of Computer Science, University of Toronto, 2005.
7. Anne Berry, Richard Krueger, Genevieve Simonet. Ultimate generalizations of LexBFS and Lex M. In Proceedings of 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), June 2005. LNCS volume 3787, 199-213.
8. Derek G. Corneil and Richard Krueger. A Unified View of Graph Searching. SIAM J. Discrete Math. Volume 22, Issue 4 (2008), pp. 1259-1276. (local prepress)
9. Ryan Hayward and Richard Krueger. Polynomial Time Line Segment Diagram Isomorphism. Eleventh SIAM Conference on Discrete Mathematics, contributed presentation, August 2002.
10. Richard Krueger. A Polynomial Time Algorithm for Line Segment Diagram Isomorphism. Masters Thesis, Department of Computing Science, University of Alberta, 2002.
11. Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part I: Theory. Journal of Formalized Mathematics, 9(1):135-142, 2001.
12. Richard Krueger, Piotr Rudnicki, and Paul Shelley. Asymptotic notation. Part II: Examples and Problems. Journal of Formalized Mathematics, 9(1):143-154, 2001.
13. Richard Krueger, Piotr Rudnicki, and Paul Shelley. O in Mizar. Proceedings of the CADE-17 Workshop on the Role of Automated Deduction in Mathematics, 12-21, June 2000.

Copyright © Richard Krueger All rights reserved. Last update: 08/30/2008 00:45:33

Computer Science