Speaker: Srinath Sridhar Time: Wednesday 12-1pm Place: NSH 1507 Title: Parameterized Algorithms for Steiner Tree Variants Abstract: Steiner tree problems naturally come up in diverse applications. It is sometimes necessary to find optimal solutions for such problems. Finding Steiner minimum trees on hypercubes is equivalent to finding the shortest evolutionary tree. In this talk, I will define two variants of the problem both of which are NP-complete. The problems can however be characterized by a parameter which is assumed to be small in practice. The first problem can be solved in time exponential in the parameter and polynomial in the size of the input. This shows that the problem is `fixed parameter tractable' (FPT). The second problem can be solved in polynomial time if the parameter is a constant. I will go over prior work and provide an overview of the algorithms.