SACT Seminar: Cartesian Tree of Tree Algorithms

Time: 1:00pm Tuesday, 31st May 2016.

Location: SIT 459

Speaker: Natalie Tridgell, University of Sydney

Title: Cartesian Tree of Tree Algorithms

Abstract:
We study the problem of constructing a cartesian tree of a tree.  We present two new algorithms for computing a cartesian tree of a tree.  We will look at worst case scenarios for four different algorithms and the performance of these algorithms.  We will also explore how this data structure can be used for problems such as for the edge-disjoint k-path centrality problem.

This was joint work with Julian Mestre.