| Title: | A Hierarchy of Graph Search Algorithms |
| Speaker: | Richard Krueger, Ph.D. Department of Computer Science University of Toronto |
| Abstract: | Graph search algorithms, such as breadth-first search or depth-first search, are widely used for problems ranging from solving mazes, to traversing graphs, to evaluating artificial intelligence search trees. Graph search algorithms visit the vertices of a graph in a particular order, which can reveal structure in the graphs. Despite the wide-spread use of these algorithms, many structural properties of these vertex orderings have not been studied. In this work, we consider the answer to a simple question: in the various types of graph search vertex orderings, how can a nonneighbouring vertex be visited before a neighbouring vertex? The surprising answers turn out to characterize a variety of known search algorithms, and leads to the identification of two new types of graph searches, completing our graph search hierarchy. We will show how this new view of graph search vertex orderings lead to applications, such as recognition of classes of graphs, finding orderings of powers of graphs, and computing minimal triangulations of graphs. Portions of this work is joint with Derek Corneil, Anne Berry and Genevieve Simonet. |
| Location: | Palenske 227 |
| Date: | 8/24/2006 |
| Time: | 3:10 PM |
@abstract{MCS:Colloquium:RichardKruegerPhD
DepartmentofComputerScience
UniversityofToronto:2006:8:24,
author = "{Richard Krueger, Ph.D.
Department of Computer Science
University of Toronto}",
title = "{A Hierarchy of Graph Search Algorithms}",
address = "{Albion College Mathematics and Computer Science Colloquium}",
month = "{24 August}",
year = "{2006}"
}