1
$\begingroup$

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


Question:

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ I imagine time roughly quadratic in the number of vertices. Start by assigning a different number to each vertex. When an edge is added, if it joins two vertices with different numbers, reassign the smaller number to all vertices with the higher number, otherwise leave things alone. You are maintaining an equivalence relation of connected components. Gerhard "Not Sure Where This Leads" Paseman, 2018.02.03. $\endgroup$
    – Gerhard Paseman
    Commented Feb 3, 2018 at 17:02
  • $\begingroup$ @GerhardPaseman I was thinking, that maybe an adaptation of the disjoint set union algorithm may yield faster algorithms. But I think that problem should have already appeared elsewhere. $\endgroup$
    – Manfred Weis
    Commented Feb 3, 2018 at 17:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .