Linear Ordering Problem of Tournament Digraph and its Computation

Abstract

A tournament is an oriented graph where every pair of distinct vertices are adjacent. It is used as a result of various competitions, such as sports league results and preference. And as ranking, there are several linear orderings at the tournament such as `Slater order', `Copeland order', `Sorted sequence of kings'. And competition winner is the first vertex of linear order. We will focus on `Slater order'.

`Slater order' is a linear order (v_1, v_2,...,v_n) of its vertex set such that

{(v_i,v_j) : i<j}

is as large as possible. In this paper, We will introduce several propositions for `Slater order' and 'Slater winner' and compare with other linear orders. And also introduce branch and bound method for computing `Slater order' of the given tournament by using boundary values of `Slater index'. Finally, we will introduce some open problems and conjecture about `Slater order'.

토너먼트란 유향그래프 중 서로 다른 두 개의 모든 꼭짓점이 한 방향으로 인접한 그래프이다. 이것은 스포츠 리그 결과나 선호도와 같은 여러 경쟁의 결과로 이용된다. 경쟁의 순위로써 토너먼트에는 Slater 순서, Copeland 순서, Sorted sequence of kings 등 여러 선형순서가 있다. 그리고 선형순서의 첫 번째 꼭짓점은 경쟁의 우승자 꼭짓점으로 불린다. 우리는 이 중 Slater order에 집중하고자 한다.

Slater 순서란 토너먼트 꼭짓점들의 선형순서 (v_1,v_2,...,v_n)중 집합 {(v_i,v_j):i<j}의 크기가 가장 큰 선형순서를 말한다. 이 논문에서는 Slater 순서와 Slater 우승자 의 여러 성질 및 다른 선형 순서와의 비교를 말하고자 한다. 또한 Slater 인덱스 의 경곗값을 이용하여 주어진 토너먼트의 Slater 순서를 계산하는 Branch and bound 방법을 보여주고자 한다. 마지막으로 특별한 예시와 열린문제를 소개한다.