Answer to Question #23280 in Discrete Mathematics 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
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.

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!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS