3
$\begingroup$

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. Let $m = |E|$ and assume the values $\{t(e): e \in E\}$ are distinct.

You wish to determine the instant $\tau$ at which the network fails.

1- Suppose you solve this problem via an intuitive algorithm in which you first sort the edges according to $t(e)$ and then remove the edges, one at a time, to determine if the network has failed. Establish the complexity of this algorithm.

My Answer: We can sort edges in $O(m\log n)$ time + removing edges takes $O(1)$ * the number of edges to be removed $O(m)$. So the complexity is $O(m^2)$.

2- Show that a variation of your intuitive algorithm from part a can determine $\tau$ in a reduced time complexity in which a factor of m is changed to log m.

My expectation: I think we might use a heap for storing edges but I am not sure how to implement it.

3- Using what you know about spanning trees, can you write a new algorithm to im­prove upon (or equal) the complexity of your algorithm from part b? (Hint: The network will be failed as soon as every spanning tree. contains a failed edge.)

My expectation: I believe we need to find all spanning trees but I am not sure if this will help reduce complexity.

Can anyone help me solving the given problem or direct me towards a reasonable solution?

$\endgroup$
0
$\begingroup$

Part b

Suppose $t(e_1)>t(e_2)>\cdots$, what you want is $e_i$ such that the graph with $e_1,\ldots,e_i$ is connected. Part a checks the graph with $e_1,\ldots,e_m$, then the graph with $e_1,\ldots,e_{m-1}$, and so on. This process can be improved by binary search, i.e. checking the graph with $e_1,\ldots,e_{m/2}$, then graph with $e_1,\ldots,e_{m/4}$ or with $e_1,\ldots,e_{3m/4}$ depending on the result of the first check, and so on.

Part c

You don't need to check all spanning trees. You only need to find the spanning tree of whose edges the earliest failure time is maximized. This is known as a minimum bottleneck spanning tree (cost of an edge is the negative of its failure time).

$\endgroup$
  • $\begingroup$ So, do you agree with me on the complexity of O(m^2) in part a ? .. that is what I am thinking about in part b but does the complexity drops to O(m log m)? $\endgroup$ – Bassem Apr 1 '18 at 12:57
  • $\begingroup$ Yes, part a is $O(m^2)$. Binary search takes only $O(\log m)$ steps while each step costs $O(m)$. $\endgroup$ – xskxzr Apr 1 '18 at 13:37
  • $\begingroup$ But, when we apply the binary search .. do we find the first instance $\tau$ in $O (m log m)$ because I believe we narrow the search but need when identifying $e_1,\ldots,e_{m/2}$ -for example- to search each arc that causes the first network disconnection .. am I right ? or my interpretation of the algorithm is wrong $\endgroup$ – Bassem Apr 1 '18 at 17:27
  • $\begingroup$ You needn't search the edge causing the network disconnected. You only check whether the graph with $e_1,\ldots,e_{m/2}$ is connected. If yes, then check $e_1,\ldots,e_{m/4}$; if no, then check $e_1,\ldots,e_{3m/4}$, and so on. $\endgroup$ – xskxzr Apr 1 '18 at 17:37
  • $\begingroup$ Oh .. I got it .. last question about part (c) .. I checked the minimum bottleneck spanning tree and found that it takes $O(m)$ time .. is that will be the complexity of the algorithm where I find minimum bottleneck spanning tree and pick the edge with the earliest failure time. or is there something more to be included ? $\endgroup$ – Bassem Apr 1 '18 at 18:05

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.