  The problem of worst case edge deletion from a network is considered. Suppose
that you have a communication network and you can delete a single edge. Which
edge deletion causes the largest disruption? More formally, given a graph,
which edge after deletion disconnects the maximum number of pairs of vertices,
where ties for number of pairs disconnected are broken by finding an edge that
increases the average shortest path length the maximum amount. This problem is
interesting both practically and theoretically. We call it the \emph{single
edge deletion problem}.
  Our contributions include formally defining the single edge deletion problem
and providing motivations from network analysis. Also, we give an algorithm
that solves the problem much faster than a naive solution. The algorithm
incorporates sophisticated and novel techniques, and generalises to the problem
of computing the all-pairs shortest paths table after deleting each edge
individually. This means the algorithm has deep theoretical interest as well as
the potential for even wider applications than those we present here.
