Given n wireless devices along with distances between each device, a number k in

Question

Given n wireless devices along with distances between each device, a number k indicating the desired size of each backup set, a number d indicating the maximum distance between a device and each of its backup sets, and a number b indicating the maximum number of devices for which a single device can serve as a backup. Find backups for all of the devices such that no device is a backup for more than b devices and each device has k backup devices within distance d of the device.

Devise an algorithm to solve this problem.

Explanation / Answer

This concept is similar to finding minimum spanning tree. Minimum spanning tree is a tree without cycles and

visit vertex only once.

So we will solve above situation using Krushkals algorithm:

KRUSKAL(G):
A = []
foreach v belongs G.V:
MAKE-SET(v)
foreach (u, v) ordered by weight(u, v), increasing:
if FIND-SET(u) FIND-SET(v):
A = A {(u, v)}
UNION(u, v)
return A

Explaination:
--------------------
Creating set S containing all edges in graph.
so until S is non empty
remove edge with minimum weight from set S
if removed edge connects two foresst trees then add it to Forest F, by combining two trees into a single tree.

Complexity of this algorithm wouldbe O(log V)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.