Springe direkt zu Inhalt

Colloquium by Benjamin Berendsohn (Freie Universität Berlin): Search trees on graphs

Nov 29, 2021 | 04:00 PM s.t.

Search trees on graphs (STGs) are a generalization of binary search trees (BSTs). Where the key space of a BST is a totally ordered set, the key space of a STG is a graph. STGs are a relatively recent notion, but have been studied previously under different names, including elimination trees, maximal tubings, and vertex rankings. We survey some results. On the computational side, we consider a model of computation for STGs analagous to the BST model, and study which known results for BSTs can be adapted. On the combinatorial side, we study the diameter of certain polytopes called graph associahedra, which can be defined via STGs.

Time & Location

Nov 29, 2021 | 04:00 PM s.t.

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)