20CS472001  Design and Analysis of Algorithms II  Winter 2011 


Instance: a graph G=(V,E), and a weighting function w:E→N^{+} Find: a cycle connecting all the vertices of V of minimum total cost.Here is a proposed (greedy) algorithm for this problem:
order edges by weight in increasing order  call the list L T ← Null (T is initialized to the empty list) while the number of edges in T is less than the number of vertices in V minus 1 do the following: e ← pop_{L} suppose e = <x,y> if there do not exist vertices a,b such that either edges <a,x> and <b,x> are in T or edges <a,y> and <b,y> are in T, and there is no path <x...y> in T then T ← T U {e} endwhile add to T the edge from L which completes the cycleShow that this algorithm can not be used to solve the Traveling Salesperson problem exactly.