Richard Krueger, Ph.D.        TO Weather    TO Weather    Babel Fish    My Yahoo!    Google    slashdot.org    UofT    SSH    TO maps
Richard Krueger Instructor
Office:   BA 4261
Phone:   416-946-8869
Fax:   416-978-1931
Email:   not available in text
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:

These are some common links that I wish I could remember, I realized I couldn't remember, and I figured would be easier to put here than to find them all from scratch every time.

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.
[University of Toronto]
Computer Science
Valid HTML 4.01!