Skip to main navigation
Skip to Content
Computer Science
University of Toronto
Quercus
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
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
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar- Mar 12
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar- Mar 12
Event date: Tuesday, March 12, 2013, at 2:10 PM
Location: PT 266
Speaker: Patrick Bennett
Carnegie Mellon University
Title: A greedy algorithm for finding a large 2-matching on a random cubic graph
Abstract:
A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U is the number of edges in U, and this is at least n - k(U) where n is the number of vertices of G and k denotes the number of components. The algorithm 2GREEDY is a greedy algorithm due to Frieze which finds a maximal 2-matching in a graph. This algorithm is similar to the well known Karp-Sipser algorithm, which finds ordinary matchings in graphs. We analyze the performance of 2GREEDY on a random 3-regular graph. Our analysis yields (more-or-less) matching upper and lower bounds on the final number of components. In particular, we prove that with high probability, the algorithm outputs a 2-matching U with k(U) = n^(1/5 + o(1)).
Joint work with Deepak Bal, Tom Bohman, and Alan Frieze (all of Carnegie Mellon University).