Suppose you work for a company that is giving a smartphone to each of its employees. Unfortunately,
Question:
Suppose you work for a company that is giving a smartphone to each of its employees. Unfortunately, the companies that make apps for these smartphones are constantly suing each other over their respective intellectual property. Say that two apps, A and B, are litigation-conflicting if A contains some disputed technology that is also contained in B. Your job is to pre-install a set of apps on the company smartphones, but you have been asked by the company lawyers to avoid installing any litigation-conflicting apps. To make your job a little easier, these lawyers have given you a graph, G, whose vertices consist of all the possible apps you might want to install and whose edges consist of all the pairs of litigationconflicting apps. An independent set of such an undirected graph, G = (V,E), is a subset, I, of V , such that no two vertices in I are adjacent. That is, if u, v ∈ I, then (u, v) ∉ E. A maximal independent set M is an independent set such that, if we were to add any additional vertex to M, then it would not be independent any longer. In the case of the graph, G, of litigation-conflicting apps, a maximal independent set in G corresponds to a set of nonconflicting apps such that if we were to add any other app to this set, it would conflict with at least one of the apps in the set. Give an efficient algorithm that computes a maximal independent set for a such a graph, G. What is the running time of your algorithm?
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia