Return to Question

Given

• a simple, symmetric, weighted graph $G(V,E,W); \text{card}(V)=n,\ \text{card}(E)=m\le\frac{n(n-1)}{2} $
• a set of ordered pairs of vertices $U=\lbrace (u_i,u_j)\rbrace\subset V\times V,\ i\lt j$
• a permutation of $\pi(E)$ that resembles an ordering of the edges

how fast can the appearance of a path between the vertices of any $(u_i,u_j)\in U$ be detected, if the edges of $G$ are inserted one by one in the order defined by $\pi(E)$ into a graph $H$, that initially only contains the set $V$ of vertices of $G$?

Answers stating the conditions, under which a specific algorithm will be fast(est) would be a great help in testing a (probably new) TSP heuristic.

Given

• a simple, symmetric graph $G(V,E); \text{card}(V)=n,\ \text{card}(E)=m\le\frac{n(n-1)}{2} $
• a set of ordered pairs of vertices $U=\lbrace (u_i,u_j)\rbrace\subset V\times V,\ i\lt j$
• a permutation of $\pi(E)$ that resembles an ordering of the edges

how fast can the appearance of a path between the vertices of any $(u_i,u_j)\in U$ be detected, if the edges of $G$ are inserted one by one in the order defined by $\pi(E)$ into a graph $H$, that initially only contains the set $V$ of vertices of $G$?

Answers stating the conditions, under which a specific algorithm will be fast(est) would be a great help in testing a (probably new) TSP heuristic.

Given

• a simple, symmetric, weighted graph $G(V,E,W); \text{card}(V)=n,\ \text{card}(E)=m\le\frac{n(n-1)}{2} $
• a set of ordered pairs of vertices $U=\lbrace (u_i,u_j)\rbrace\subset V\times V,\ i\lt j$
• a permutation of $\pi(E)$ that resembles an ordering of the edges

how fast can the appearance of a path between any $(u_i,u_j)\in U$ be detected, if the edges of $G$ are inserted one by one in the order defined by $\pi(E)$ into a graph $H$, that initially only contains the set $V$ of vertices of $G$?

Answers stating the conditions, under which a specific algorithm will be fast(est) would be a great help in testing a (probably new) TSP heuristic.

Given

• a simple, symmetric, weighted graph $G(V,E,W); \text{card}(V)=n,\ \text{card}(E)=m\le\frac{n(n-1)}{2} $
• a set of ordered pairs of vertices $U=\lbrace (u_i,u_j)\rbrace\subset V\times V,\ i\lt j$
• a permutation of $\pi(E)$ that resembles an ordering of the edges

how fast can the appearance of a path between the vertices of any $(u_i,u_j)\in U$ be detected, if the edges of $G$ are inserted one by one in the order defined by $\pi(E)$ into a graph $H$, that initially only contains the set $V$ of vertices of $G$?

Answers stating the conditions, under which a specific algorithm will be fast(est) would be a great help in testing a (probably new) TSP heuristic.