Analysis of Algorithms : An Active Learning Approach

9.1 GREEDY APPROXIMATION ALGORITHMS 239

a polynomial algorithm that could color any graph with no more than twice as

many colors as optimal, there would be a polynomial algorithm that could

color any graph optimally. This would mean that P = NP. There are some

restrictions that can be placed on the complexity of graphs that make it easier

for them to be colored. For example, if a graph is planar, in other words, when

drawn in one plane none of its edges cross, there are algorithms that can color

it within polynomial time.

A simple algorithm to color any graph with N nodes uses a sequential col-

oring method. An algorithm for this is

ColorGraph( G )
G the graph to be colored

for i = 1 to N do
c = 1
while there is a node in G adjacent to nodei that is colored c do
c = c + 1
end while
color nodei with c
end for

The degree of a graph is the largest number of edges leaving one node. This

coloring algorithm will use C colors where C is 1 greater than the degree of

the graph. It is possible to do better than this, but the algorithm is beyond the

scope of this book.

9.1.6

1. What path would the greedy traveling salesperson algorithm find if the city
   matrix is

Is the path it finds optimal?

2. Another technique for bin packing is best fit, where each item is placed in
   the bin so that the least amount of space is left over. New bins are started

9.3.3 Exercises

From To234567

1 5 1 2 16 17 21

2 10718815

3 9 11 13 4

4 3 20 14

5126

619