Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling

Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling

  • Lijun Chang, Wei Li, Wenjie Zhang
  • SIGMOD 2017

概要だけ

  • 最大独立集合をほぼ線形時間で近似計算
  • 低次数は飛ばす
  • 高次数は含まれにくい
  • 主なreduction: degree1, degree2, inexact reduction(厳密性を犠牲にする)
  • 少し省メモリにして格納
  • 線形時間:Degree-two path reductionなるものを提案
  • Δ×線形時間:Dominance reductionなるものを提案
  • 実験で色々検証
    • ちなみにground truthは[Akiba-Iwata. '16]で計算

まとめ

  • こういう内容もグラフDBで評価されるのだなぁ…

2017/05/27

最終更新:2017年05月27日 22:47