Return to Question

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$. You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points.

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$. 

You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points. That is, every vertex $v$ corresponds to some point $(x,y)$ in the plane, and for an edge $(u,v)=((x_1,y_1),(x_2,y_2))$ its weight is equal to $\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph. Furthermore, its weight is shorter than the shortest path between $u$ and $v$. You may assume that the distances are Euclidian.

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$. You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points.

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved?

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph. Furthermore, its weight is shorter than the shortest path between $u$ and $v$. You may assume that the distances are Euclidian.

Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph. Furthermore, its weight is shorter than the shortest path between $u$ and $v$. You may assume that the distances are Euclidian.