Hello,

I know next to nothing about graph theory, but in my work I have encountered an application for which I would like to do the following: Given a connected graph $G$ and integer $k > 0$, add a set of $k$ edges ("shortcuts") to $G$ to minimize the average "travel" distance on $G$ between vertices. Here, every edge has equal weight. I do not desire a provably minimal solution, but I would rather accept a slightly sub-optimal set of shortcuts if it meant that I could greatly lower the computation time.

A quick Google search yields two interesting papers, http://www.cs.ucla.edu/~awm/papers/APPROX09-NoC.pdf and dspace.mit.edu/openaccess-disseminate/1721.1/62215, one of which addresses my problem directly and another that tackles a related problem (minimizing diameter).

However, because I know little about graph theory, I was wondering if there might be other papers that I might find, or even textbook references, if there are any special cases for which this problem is significantly easier (as the graph I have is far from typical, and I suspect it has some nice properties).