W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Mathematics Colloquium and EXTREEMS-QED Lecture: Frans Schalekamp (College of William and Mary)
December 5, 2014
2pm - 3pm
Abstract: Consider the following graph theoretic problem: We are given two rooted trees with the same leaf sets as input, and want to find the minimum number of edges to cut from both trees, so that the components after cutting these edges have the same structure (modulo edge contractions). This problem is known as the Maximum Agreement Forest Problem, and has its roots in biology and genetics, where the solution to the problem is proposed as a measure to compare phylogenetic trees. Not surprisingly, this problem is NP-hard. I will present the ideas behind a novel approximation algorithm for the Maximum Agreement Forest Problem that is simpler and better than previous algorithms for this problem.
This is joint work with Anke van Zuylen, Neil Olver, Suzanne van der Ster and Leen Stougie.
This is joint work with Anke van Zuylen, Neil Olver, Suzanne van der Ster and Leen Stougie.
Contact
Junping Shi