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.