Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a way to determine how the average geodesic distance between nodes of a graph will change just by flipping (1) a single edge without having to traverse the whole graph like in the Djikstra algorithm?

I'm currently doing this by expensively copying the graph, changing the edge, and then calculating the average geodesic distance of the new graph (using Dijkstra's algorithm) and subtracting it from the average geodesic distance of the original graph..

Is there a more clever way to to this?

notes:

(1) By flipping a edge I mean the following operation: add the edge if it's absent and remove it if it's present.

(2) Good approximations are welcomed. It's part of a Monte Carlo simulation, so I must repeat this calculation many, many times.

share|improve this question
    
An idle question: could it be true that if the average change in distance is low enough, then your graph is an expander? (This question will not help solve the original question, which is about efficiently computing the average change.) –  Tom Church May 21 '11 at 16:30
1  
Tom: it could be that the graph consists of 2 parts with 2 edges between them such that you would have to go through one of these edges, but neither is pivotal - removing either would not change the average at all. –  Ori Gurel-Gurevich May 21 '11 at 19:20

1 Answer 1

up vote 2 down vote accepted

With the right data structures (see http://www.ams.org/mathscinet-getitem?mr=2145260), one can maintain a matrix of pairwise distances between vertices in a dynamic graph. Updating the entire matrix after modifying an edge takes $O(n^2\log^3n)$ (amortized). This is at least better than doing a completely new all-pairs shortest path algorithm each time you modify an edge.

I don't, however, see an easy way to take advantage of the fact that you are not interested in the entire matrix of distances, but rather just the average distance.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.