Reference no: EM133300637

Question

Let G(V, E) be a graph with positive weights on its edges. For a vertex v ∈ V,, and r > 0 let us define the ball B(v, r) center at v and of radius r as the set of all vertices whose distance from v is ≤ r B(v, r) = {u ∈ V | δ(v, u) ≤ r} Where δ(u, v) is the minimum sum of weights of edges along any path u → v. Assume r is a fixed integer. Suggest an algorithm with a running time as efficient as possible that finds 17 such balls, whose union contains as many vertices as possible. What could you say about the approximation factor that you'd obtain? State as accurately as possible your algorithm's performances. Try to implement this algorithm reasonably efficiently (but without scarifying the approximation factor)