BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Search trees on graphs (STGs) are a generalization of binary s
earch 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\, b
ut have been studied previously under different names\, including eliminati
on trees\, maximal tubings\, and vertex rankings. We survey some results. O
n the computational side\, we consider a model of computation for STGs anal
agous to the BST model\, and study which known results for BSTs can be adap
ted. On the combinatorial side\, we study the diameter of certain polytopes
called graph associahedra\, which can be defined via STGs.
DTSTAMP:20211104T170300
DTSTART:20211129T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)\n
SEQUENCE:0
SUMMARY:Benjamin Berendsohn (Freie Universität Berlin): Search trees on gra
phs
UID:107919437@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20211129-C-Berendsohn.html
END:VEVENT
END:VCALENDAR