***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Stoyan Dimitrov (Rutgers)

Thursday 12th September, 3:00 in Fine Hall 224.

Title: BFS versus DFS for random targets in ordered trees

We consider the average time complexity of breadth-first search (BFS) and
depth-first search (DFS), when we have a uniformly random target node
selected among all nodes at level m in all ordered trees with n edges.
Intuition suggests that for a fixed n, BFS should have better average
performance when m is small, while DFS must have an advantage when m 
is large. But where exactly is the threshold, for m as a function of n, 
and is it unique? We answer this question by using results on the 
occupation measure of Brownian excursions and an identity related to 
lattice paths. At the end we ask some interesting further questions.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)