Speaker: Bruce Reed
Department of Computer Science
Title: A Linear Time Algorithm For the 2 Disjoint Rooted Paths Problem
Abstract: The 2-Disjoint Rooted Path Problem asks for vertices $s_1,s_2,t_1,t_2$ in a graph $G$, whether there are vertex disjoint paths $P_1$ and $P_2$ such that $P_i$ has endpoints $s_i$ and $t_i$. We present a new linear time algorithm for this problem (this is joint work with Rohan Kapadia and Zhentao Li). The techniques we use form part of an arsenal of tools which yield an $O(n log n)$ algorithm for the general $k$-DRP Problem which we touch on briefly (this is joint work with Kenichi Kawarabayashi).
Talk sponsored by: Michael Molloy