Speaker
Ramin Mousavi
Description
Zachary Friggstad and Ramin Mousavi
Abstract: We present an $O(\log k)$-approximation for both the edge-weighted and node-weighted versions of \DST in planar graphs where $k$ is the number of terminals. We extend our approach to \MDST\footnote{In general graphs \MDST and \DST are easily seen to be equivalent but in planar graphs this is not the case necessarily.}, in which we get a $O(R+\log k)$-approximation for planar graphs for where $R$ is the number of roots.