| DATE: | Wednesday, October 22nd |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnell 320 |
| TITLE: | On traversal sequences and graph s-t-connectivity |
| SPEAKER: | Michal Koucky, Department of Computer Science at Rutgers University. |
Traversal sequences are sequences of labels used to navigate in
a graph. They are the main tool in study of space complexity of
undirected s-t-connectivity (which is a fundamental algorithmic
problem). In this talk we will introduce you to the concept, we
will survey what is known about traversal sequences and their
relatives (exploration sequences) and we will list many
interesting open problems pertaining this area ranging from
combinatorics to computational complexity.