Which of the following problems can be solved by a standard greedy algorithm?
I. Finding a minimum spanning tree in an undirected graph with positive-integer edge weights
II. Finding a maximum clique in an undirected graph
III. Finding a maximum flow from a source node to a sink node in a directed graph with positive-integer edge
capacities
(A) I only (B) II only (C) III only (D) I and II only (E) I, II, and III
1
Expert's answer
2013-02-01T10:01:41-0500
Finding a minimum spanning tree in an undirectedgraph with positive-integer edge weights -- The classical algorithm for solving this problem is Kruskal's algorithm. Also, Kruskal's algorithm is, again, classical example of greedy algorithm. So, we can cross out (B) and (C). Finding a maximum clique in an undirected graph -- NP-complete problem, that couldn't solved, in general, by any polynomial (and as a result, greedy) algorithm. According to this, we can cross out (D) and (E). This explanation use only definitions and all known facts. A low-level strict proof is much more harder problem that could be needed in such questions.
Numbers and figures are an essential part of our world, necessary for almost everything we do every day. As important…
APPROVED BY CLIENTS
"assignmentexpert.com" is professional group of people in Math subjects! They did assignments in very high level of mathematical modelling in the best quality. Thanks a lot
Comments
Leave a comment