Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> NOV 20: DCS Combinatorics Seminar *UPDATED
About
Undergraduate
Graduate
Research
People
News & Events
NOV 20: DCS Combinatorics Seminar *UPDATED
Event date: Friday, November 20, 2009, at 1:10 PM
Location: Galbraith Bldg, Rm. 221 *UPDATED
Speaker: Bruce Reed
Department of Computer Science
McGill University
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