中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

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

:::

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

  • 講者蔡孟宗 教授 (國立交通大學資訊工程系)
    邀請人:TIGP SNHCC Program
  • 時間2017-12-06 (Wed.) 14:00 ~ 16:00
  • 地點資訊所舊館108演講廳
摘要

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.