This survey provides a guiding reference to researchers seeking an overview of the large
body of literature about graph spanners. It surveys the current literature covering various …

We consider several well-studied problems in dynamic algorithms and prove that sufficient
progress on any of them would imply a breakthrough on one of five major open problems in …

'Network'is a heavily overloaded term, so that 'network analysis' means different things to
different people. Specific forms of network analysis are used in the study of diverse …

A shortest-path algorithm finds a path containing the minimal cost between two vertices in a
graph. A plethora of shortest-path algorithms is studied in the literature that span across …

Let G=(V, E) be an undirected weighted graph with| V|= n and| E|= m. Let k≥ 1 be an
integer. We show that G=(V, E) can be preprocessed in O (kmn 1/k) expected time …

Betweenness centrality is a fundamental measure in social network analysis, expressing the
importance or influence of individual vertices in a network in terms of the fraction of shortest …

The diameter and the radius of a graph are fundamental topological parameters that have
many important practical applications in real world networks. The fastest combinatorial …

We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for
weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first …

The radius and diameter are fundamental graph parameters, with several natural definitions
for directed graphs. Each definition is well-motivated in a variety of applications. All versions …

Let G=(V, E) be an unweighted undirected graph on n vertices. A simple argument shows
that computing all distances in G with an additive one-sided error of at most 1 is as hard as …