# 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

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

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.

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.

## Comments

## Leave a comment