# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 16.6.2011 at 13:00 in S6, there is the following noon lecture:

# Characterizing Path Graphs and Directed Path Graphs using PR-trees

## Steven Chaplick

## University of Toronto

## Abstract

A new data structure, the PR-tree, is introduced to characterize the sets of path-tree models of path graphs. We further characterize the sets of directed path-tree models of directed path graphs with a slight modification to the PR-tree. The characterizations are proven constructively. A careful examination of the algorithmic approach used in the construction shows that a PR-tree that captures the path-tree models of a given graph with n vertices and m edges can be performed in O(a(n+m) * n * m) (where a(s) is the inverse of Ackermann's function arising from Union-Find). Additionally, the size of any PR-tree which is produced by this approach is linear with respect to input graph.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page