Using Approximation Algorithm of Minimum Steiner Tree to Implement Connected Identifying Code - 02/04/2011

Wei Si

In this talk, we will first review over the concept of ID-code and connected ID-code, which Niloofar has been working on. Then we will introduce the problem of Minimum Steiner Tree and illustrate an approximation algorithm to solve the problem.

Finally, we will see how the approximation algorithm will be used in the connected ID-code problem. However, we still need to wait until the experiment is finished to see whether there is improvement on the size of connected ID-code.

-- JiaxiJin - 09 Feb 2011