ICS Theory Group

ICS 269, Winter 2006: Theory Seminar

Feb 10, 2006, in CS 253

Simultaneous Source Location on Trees

Presented by Josiah Carlson


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.