52 839
Assignments Done
Successfully Done
In October 2017
Your physics homework can be a real challenge, and the due date can be really close — feel free to use our assistance and get the desired result.
Be sure that math assignments completed by our experts will be error-free and done according to your instructions specified in the submitted order form.
Our experts will gladly share their knowledge and help you with programming homework. Keep up with the world’s newest programming trends.

Answer on Discrete Mathematics Question for Sujata Roy

Question #23280
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
(A) I only (B) II only (C) III only (D) I and II only (E) I, II, and III
Expert's answer
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.

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!


No comments. Be first!

Leave a comment

Ask Your question