Institute of Information Science, Academia Sinica



Press Ctrl+P to print from browser


TIGP (SNHCC) -- Streaming Algorithms for Certain Spanning Trees

  • LecturerProf. Meng-Tsung Tsai (Dept. of Computer Science, National Chiao Tung University)
    Host: TIGP SNHCC Program
  • Time2017-12-06 (Wed.) 14:00 – 16:00
  • LocationAuditorium 108 at IIS Old Building

Physical memory is small. When the input graph has size greater than memory size, almost all graph problems become difficult to solve. However, the minimum spanning tree problem is an extraordinary example that can be solved optimally even if the input graph cannot be kept entirely in memory. We are curious whether other well-known spanning tree problems are easy to solve when memory space is not enough.


In this talk, we will see how to find a good approximate solution for the maximum leaf spanning tree problem and the minimum diameter spanning tree problem using small space. Formally, our algorithms use O(n log n) space for n-node graphs. We will also show that no algorithm in the standard streaming model can find an exact solution for these two problems unless Ω(n 2) space is affordable.