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]で計算
まとめ
2017/05/27
最終更新:2017年05月27日 22:47