235 citations · 345 across the 30 of their papers we have counts for
3 papers · 1 filter
Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
Satoshi Takabe, Takafumi Nakano, Tadashi Wadayama
The fault tolerance of random graphs with unbounded degrees with respect to connectivity is investigated, which relates to the reliability of wireless sensor networks with unreliab…
Typical Approximation Performance for Maximum Coverage Problem
Satoshi Takabe, Takanori Maehara, Koji Hukushima
This study investigated typical performance of approximation algorithms known as belief propagation, greedy algorithm, and linear-programming relaxation for maximum coverage proble…
An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
Jun Takahashi, Satoshi Takabe, Koji Hukushima
A recently proposed exact algorithm for the maximum independent set problem is analyzed. The typical running time is improved exponentially in some parameter regions compared to si…