215 citations · 689 across the 60 of their papers we have counts for
4 papers · 1 filter
Distributed Algorithms for Large-Scale Graphs
Khalid Hourani, Hartmut Klauck, William K. Moses +4
Motivated by the increasing need for fast processing of large-scale graphs, we study a number of fundamental graph problems in a message-passing model for distributed computing, ca…
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the maximum…
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
We study dynamic -approximation algorithms for the all-pairs shortest paths problem in unweighted undirected -node -edge graphs under edge deletions. The fastest algor…
Distributed Random Walks
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan +1
Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this paper, we foc…