Abstract:
We describe the Simultaneous Source Location problem on Trees. We provide an algorithm which solves the problem in O(n2) time and space, which improves upon a previous O(n3) time and O(n2) space algorithm. We also provide an algorithm that solves a variant of this problem in O(n) time and O(depth(G)*degree(G)) space.