Speaker: Hieu Dinh
Day:  Wednesday, 11/07/2007
Room: ITEB 336
Time: 2:00-3:00pm

Title: Approximation algorithms for Telephone Broadcast Problem and Poise
Problem.

Abstract: In networks, broadcasting is a fundamental operation a single
message has to be sent from a source node to all other nodes. There have
been extensive studies on broadcasting under several models. In this talk,
we consider the broadcast problem in telephone model. We will discuss the
first O(log^2 n/log log n)-approximation algorithm for the broadcast
problem. Also, we will talk about the connection between the broadcast
problem and the poise of a graph.


Reference: Rapid Rumor Ramification- Approximating the minimum broadcast
time, Ravi R., FOCS 1994.