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

活動訊息

友善列印

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

保持參數化超邊連通度的稀疏化演算法

:::

保持參數化超邊連通度的稀疏化演算法

  • 講者黃上恩 博士 (波士頓學院)
    邀請人:蔡孟宗
  • 時間2022-08-24 (Wed.) 10:00 ~ 12:00
  • 地點資訊所新館106演講廳
摘要
圖 (graphs) 的稀疏化 (sparsification) 意旨於利用較少的資訊量保存(或近似)我們在原圖上關注的某項性質,比如距離 (distances) 與連通度(connectivity) 等。這些稀疏化的圖,不只能降低儲存特定性質所需要的空間,還能被應用在一些動態圖 (dynamic graph) 相關的問題中。
        在本次的演講中,我們關心以下的問題:在一個無向無權圖 G 中給定一個被稱為終端集 (terminal set) 的點集合 T,我們想建構一個較稀疏的圖 H,保存 T 中所有不超過參數 c 的最小割之劃分。
        [Chalermsook et al., SODA'21] 與 [Liu, 2020] 給出了在一個解決該問題的稀疏化演算法,其建構出的圖 H 僅包含 O(|T|c^3) 條邊,與原圖的點數和邊數無關。我們 [Han et al., ESA'22] 將其結果延伸至超圖 (hypergraphs),並利用有趣的小技巧建構出僅包含 O(|T|c^3) 條超邊並保持超邊連通度的稀疏圖,值得注意的是,建構出的圖上其邊數大小與超邊的秩無關。
        詳情請參考 https://arxiv.org/pdf/2207.04115.pdf .