Computer Science Graph Algorithm Design

Do My Homework Service Links: Online Assignment Help, Do My Assignments Online -

You have been hired by the university to manage the

wireless network across campus. The network is set up as follows: there is one modem and many

routers, which need to be connected together by cables. A router can only function if there is

some path of cables (possibly through other routers) that connects it to the modem. Your job is to

establish this network and keep all the routers functioning properly. There are many cables already

in place between the routers, but they are old and malfunctioning. It is not within your budget

to replace them with new cables, and so you will need to manage this network by repairing faulty

cables. (Assume that it is possible to connect the whole network with these faulty cables, and that

all the cables can carry data in both directions.)

You think back to what you learned in 240, and remember that you can use DFS to find a tree

that connects every router to the modem. So, you run DFS from the modem (faulty cables are

edges and the routers/modem are vertices) and repair all the tree edges of the DFS tree. Good

job! We will denote this tree of now functioning cables as T .

However, since these cables are old and prone to failure, one of them might stop working at

any time! Therefore, the university wants to know how many malfunctioning cables can potentially

replace a repaired cable in case it permanently fails. To formalize this, let e be some repaired cable.

If this cable were removed, T would be split into two connected components. The modem would

be in one of these components, and all the routers in the other component would no longer be

connected to the modem! However, there may be other malfunctioning cables that connect these

two components; therefore, repairing one of those cables will reconnect the network. The university

wants to know how many such malfunctioning cables are there for each repaired cable.

Give an algorithm that computes all these counts (one for each edge in T ) in O(m) time, where

m is the total number of cables, both repaired and malfunctioning. You may assume that for a

pair of routers/modem u and v, you can determine if u is an ancestor of v in T in O(1) time.

(Hint: Recall that there are no cross edges in an undirected graph with respect to any DFS

tree.) 


Please include proof of correctness.

Get Help With a similar task to - Computer Science Graph Algorithm Design

Related Questions

Find Related Questions Here