General rumor blocking: an efficient random algorithm with martingale approach (Q6073044)

This paper studies general rumor blocking with an eye on an efficient random algorithm with martingale approach. The general rumor blocking problem is presented and a greedy algorithm is described which returns a \(1-e^{-1}\)-approximate solution. An efficient random algorithm R-GRB is proposed for general rumor blocking problem. The approximate ratio and time complexity are analyzed based on the tools of reverse methods and martingale's method. For the entire collection see [Zbl 1400.68037].