Institute of Information Science, Academia Sinica

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.