2
$\begingroup$

I have an undirected graph, where the value of the path is the maximum weight among all weights edges included in it. And I want find the path of minimum value between two given vertices in time $O(n + m)$, where $n$ - number of vertices, $m$ - number of edges.

$\endgroup$
1
$\begingroup$

I will use the fact that you can check for the connectivity between two vertices $s$ and $t$ in a graph with $m>0$ edges in time $O(m)$.

Call $G$ be the input graph, and let $s$ and $t$ be endpoints of the paths you are interested in. I will denote by $G_w$ (resp. $G^<_w$) the graph induced by all the edges of weight at most (resp. less than) $w$ in $G$. You can solve the problem using the following recursive algorithm:

If $G$ has no edges, report that $s$ and $t$ are disconnected in $G$.

If $G$ has at least one edge, find the median $w$ among the edge weights of $G$, and proceed as follows:

  • If $s$ and $t$ are connected in $G_w$ and disconnected in $G^<_w$, return $w$.

  • If $s$ and $t$ are connected in both $G_w$ and $G^<_w$, apply the algorithm recursively on $G^<_w$ (notice that $G^<_w$ has at most $\frac{m}{2}$ edges).

  • If $s$ and $t$ are disconnected in $G_w$, build the graph $G'$ obtained from $G$ by identifying all vertices that belong to the same connected component of $G_w$, and apply the algorithm recursively on $G'$ (notice that $G'$ has at most $\frac{m}{2}$ edges, since it can't contain any edge with weight less than or equal to $w$).

The time complexity of the above algorithm is described by the recurrence equation: $T(m) = T(m/2) + O(m)$, which has solution $T(m)=O(m)$.

This problem is the same as its maximization version once all edge weights are multiplied by $-1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You can explain what the cases mean: "Otherwise", "If this is not the case"? How do these cases differ? $\endgroup$ – Kapa Apr 26 at 11:20
  • $\begingroup$ I explicitly stated the condition for each of the cases. Is this clear now? $\endgroup$ – Steven Apr 26 at 12:50
  • $\begingroup$ Everything is clear, but what is the difference between $G_w$ and $G_w^{<}$ $\endgroup$ – Kapa Apr 26 at 14:13
  • $\begingroup$ $G_w$ is the graph induced by all the edges of weight at most $w$ in $G$. $G^<_w$ is the graph induced by all the edges of weight smaller than $w$ in $G$. An edge of weight $w$ is in $G_w$ but not in $G^<_w$. $\endgroup$ – Steven Apr 26 at 14:27
  • $\begingroup$ Maybe I'm wrong, but we run the procedure twice at each stage, and the recurrence equality will be different. $\endgroup$ – Kapa Apr 29 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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