The problem of the moody chess players

F.J. Bult, van de, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

Abstract

We analyze a sorting problem where for every element there is a hard upper bound on the overall number of lost comparisons: Given are n elements and n non-negative integers a1,…,an. The goal is to sort these n elements by pairwise comparisons, subject to the condition that the kth element must not be the loser (= smaller element) in more than ak of its comparisons against the other elements. We completely characterize the sequences a1,…,an for which this sorting problem can be solved.
Original languageEnglish
Pages (from-to)336-337
JournalInformation Processing Letters
Volume108
Issue number5
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'The problem of the moody chess players'. Together they form a unique fingerprint.

Cite this