## February 19, Winter Quarter 2010: Theory Seminar

### 1:00pm in 1423 Bren Hall

#
Applications of Forbidden 0-1 Matrices to Search Tree and Path
Compression-Based Data Structures

## Pawel Pszona, UC Irvine

Presenting a paper by Seth Pettie, from SODA 2010

Abstract: In this paper we improve, reprove, and simplify a variety
of theorems
concerning the performance of data structures based on path
compression and
search trees. We apply a technique very familiar to computational
geometers
but still foreign to many researchers in (non-geometric) algorithms
and data
structures, namely, to bound the complexity of an object via its
forbidden substructures.

To analyze an algorithm or data structure in the forbidden
substructure
framework one proceeds in three discrete steps. First, one
transcribes the
behavior of the algorithm as some combinatorial object $M$; for
example, $M$
may be a graph, sequence, permutation, matrix, set system, or tree.
(The size
of $M$ should ideally be linear in the running time.) Second, one
shows that $M$
excludes some forbidden substructure $P$, and third, one bounds the
size of
any object avoiding this substructure. The power of this framework
derives
from the fact that $M$ lies in a more pristine environment and that
upper bounds
on the size of a $P$-free object $M$ may be taken "off the shelf".