Sorting a sequence of strong kings in a tournament

✍ Scribed by Ting-Yem Ho; Jou-Ming Chang

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 79 KB
• Volume: 87
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(03)00346-6

✦ Synopsis

A king in a tournament is a player who beats any other player directly or indirectly. According to the existence of a king in every tournament, Wu and Sheng [Inform. Process. Lett. 79 (2001) 297-299] recently presented an algorithm for finding a sorted sequence of kings in a tournament of size n, i.e., a sequence of players u 1 , u 2 , . . . , u n such that u i → u i+1 (u i beats u i+1 ) and u i is a king in the sub-tournament induced by {u i , u i+1 , . . . , u n } for each i = 1, 2, . . . , n -1. With each pair u, v of players in a tournament, let b(u, v) denote the number of third players used for u to beat v indirectly. Then, a king u is called a strong king if the following condition is fulfilled: if v → u then b (u, v) > b(v, u). In the sequel, we will show that the algorithm proposed by Wu and Sheng indeed generates a sorted sequence of strong kings, which is more restricted than the previous one.