Newsgroups: ut.theory
Path: utzoo!utgpu!jarvis.csri.toronto.edu!ai.toronto.edu!nishi
From: nishi@ai.toronto.edu (Naomi Nishimura)
Subject: student seminar
Message-ID: <1988Feb29.123538.11710@jarvis.csri.toronto.edu>
Organization: Department of Computer Science, University of Toronto
Date: Mon, 29-Feb-88 12:35:38 EST

This week's speaker will be Teresa Przytycka, who will talk about parallel
algorithms on trees and their application to graph problems.
The meeting will be held in Wallberg 144 from 11:00-12:00 on Thursday, 
March 4.

The talk will be based on two papers: "A Simple Parallel Tree Contraction
Algorithm" by K.Abrahamson, N.Dadoun, D.Kirkpatrick, and T.Przytycka,
and "Parallel Recognition of Complement Reducible Graphs and Cotree
Contraction" by D.Kirkpatrick and T.Przytycka.  The tree contraction 
problem is the problem of reducing a rooted tree to its root by a sequence 
of independent vertex removals. Parallel tree contraction may be 
considered as the base for many parallel algorithms on trees. In particular,
it may be used for computing graph functions for those families of graphs
which have tree representations.