15 citations · 42 across the 8 of their papers we have counts for
6 papers · 1 filter
Distributed Algorithms for Directed Betweenness Centrality and All Pairs Shortest Paths
Matteo Pontecorvi, Vijaya Ramachandran
The betweenness centrality (BC) of a node in a network (or graph) is a measure of its importance in the network. BC is widely used in a large number of environments such as social…
A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Rounds
Udit Agarwal, Vijaya Ramachandran, Valerie King +1
We present a deterministic distributed algorithm to compute all-pairs shortest paths(APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in $\tilde{O}(n^{3/2…
A Faster Algorithm for Fully Dynamic Betweenness Centrality
Matteo Pontecorvi, Vijaya Ramachandran
We present a new fully dynamic algorithm for maintaining betweenness centrality (BC) of vertices in a directed graph with positive edge weights. BC is a widely used param…
Fully Dynamic All Pairs All Shortest Paths
Matteo Pontecorvi, Vijaya Ramachandran
We consider the all pairs all shortest paths (APASP) problem, which maintains all of the multiple shortest paths for every vertex pair in a directed graph with a positive…
Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran
We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G=(V,E) with positive edge weights. F…
Betweenness Centrality -- Incremental and Faster
Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran
We consider the incremental computation of the betweenness centrality of all vertices in a large complex network modeled as a graph G = (V, E), directed or undirected, with positiv…