Event Details
Maximum Capacity Broadcast
Presenter: Mohammad Salavatipour - Department of Computer Science, University of Toronto
Supervisor: R. Nigel Horspool, Chair, Department of Computer Science
Date: Thu, March 13, 2003
Time: 13:30:00 - 14:30:00
Place: Engineering Office Wing Building (EOW) Room # 430
ABSTRACT
ABSTRACT:
Consider the following scenario: in a network N having n nodes there is a broadcaster B which wants to send some big data streams to k other nodes that are the receivers (k<=n-1). Each of the other nodes in the network are routers and pass the streams they receive on to adjacent nodes. Therefore, each data stream will traverse a tree which contains all the receivers and starts at B. Due to the huge sizes of the streams, no two of them can traverse a network link at the same time. Therefore, for each data stream we have to find a different tree, disjoint from the others.
The goal is to send the maximum number of different data streams through the network. These trees are known as Steiner trees and the problem of packing Steiner trees is a generalization of two fundamental theorems in graph theory. We talk about the first linear approximation algorithm for this problem.
Note: Mr. Salavatipour is a candidate for a faculty position in the Department of Computer Science.