he problem of ranking players in a tournament has been the subject of various research investigations. This tournament structure also arises in other environments like the problems of soliciting customer preferences of a set of products, establishing funding priorities of a set of projects [5], establishing searching priorities for a set of search engines in the internet. It is known that the results of a tournament can be represented in adigraph, G=(V, A) known as tournament graph, where vertices correspond to players and arcs correspond to match results. A tournament result is said to be upset (or violation) if a lowly-ranked player has defeated a highly-ranked player. Ali [1], Cook [6], Goddard [5], Poljak [3] and many others have concentrated on the problem of determining ranks based on the results of the tournament. A constructive lower bound on the tournament ranking function was obtained in [4]. In [2], a heuristic solution to optimize the number of violations has been developed. This paper presents a new version of MST algorithm which reduces the number of violations compared to MST algorithm. The problem of minimizing the number of upsets is equivalent to finding the minimum number of arcs in adigraph deletion of which results in an acyclic digraph.

Before describing the new algorithm, we present here a brief discussion on MST algorithm [2] and GIK algorithm [1]. MST: For ease of discussion we recapitulate some of the definitions used in MST algorithm.

1. cutset(i, k, j) -is the difference between the numbers of outgoing arcs from set (i, k) to set (k + 1, j) and outgoing arcs from set (k + 1, j) to set (i, j), where set (i, j) is the set of vertices corresponding to players ranked from i to j. 2. maxwin(i, j) -is the maximum number of wins of a player in set (i, j). 3. pair(i, j) -corresponds to an upset if the player ranked j defeats the player ranked i. MST () Repeat until swap = false swap ?false for i= 1 to size-1 do for j = i + 1 to size do for k=i to j-

This problem is knownas Minimum Feedback Arc set Problem, and is NP-hard for general digraphs [1].

Assuming the number of players in the tournament to be n, complexity of the MST algorithm can be derived as follows: In the k-loop, calculation of cutset value requires O(n) operations. Each of the i, j and k-loop will be done at most n times for a single swap, which will reduce the number of violations by 1. The amount of computation for this is at most O(n 4 ). Since there can be at most O(n 2 ) violations initially, the algorithm requires at most O(n 6 ) calculations.

When applying the IK algorithm to rank a tournament, two basic steps are executed in case of a tie. The first attempts to break the tie by restoring the players, while the second (which is applied when the first step fails) randomly ranks the players involved in the tie. The GIK algorithm differs from the IK procedure in these two steps. The restoring method is different, and if this restoring method does not resolve the ties, an attempt is made to rank the players in a manner that will reduce the overall number of violations.

The GIK algorithm appears below.

Let R = á´?", A = {P

In this Section we propose A new version of MST algorithm that results in minimum number of upset compared to the MST algorithm and GIK algorithm for ranking players in a round-robin tournament [].

We consider only simple connected digraphs G=(V,A). Spanning trees of any digraph are denoted by T. A directed cutset(V i ,V j ) is defined as

For improvement of the algorithm we introduce the following symbols and functions: Sa -start of setA Ea -end of setA Sb -start of setB Eb -end of setB Sc -start of setC Ec -end of setC Cutset(A,B)-is the difference between the numbers of outgoing arcs from set A to set B and outgoing arcs from set B to set A.

Cutset(A,C)-is the difference between the numbers of outgoing arcs from set A to set C and outgoing arcs from set B to set A.

Cutset(B,C)-is the difference between the numbers of outgoing arcs from set B to set C and outgoing arcs from set C to set B.

Procedure: Improved MST 3.

5.

7. 8.

10.

12. 13.

14. 15. 16.

The new_MST Algorithm has been compared with MST Algorithm and the GIK algorithm on the basis of a set of randomly generated tournaments of sizes ranging from 5 to 50 players. All algorithms have been programmed in C and runs were made on a core i3 machines. We have been measured both in terms of violations and computational time. Here new_MST gives better result compared to MST and GIK with respect to number of violations.