ICS 269, Winter 2006: Theory Seminar

Feb 10, 2006, in CS 253

Simultaneous Source Location on Trees

Presented by Josiah Carlson

Abstract:

We describe the Simultaneous Source Location problem on Trees. We provide an algorithm which solves the problem in O(n²) time and space, which improves upon a previous O(n³) time and O(n²) 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.