A Consideration of a Score Sequence Problem of a Tournament
| Autor: | TAKAHASHI, Masaya |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 1996 |
| Předmět: | |
| Zdroj: | 福岡工業大学研究論集. 28(2):221-227 |
| ISSN: | 0287-6620 |
| Popis: | application/pdf 論文(Article) A sequence of nonnegative integers S=(s₁, s₂, · · · ·, sn) is a score sequence of a k-tourna ment if, for some positive integer k, there is a directed graph with vertices v₁, v₂, · · · ·, Vn such that deg+(vj=s; and deg一(vj)=k(n-1)-s; for each i=1, 2, · · · ·, n. The score sequence problem of a k-tournament is: Given some positive integer k and a sequence of nonnegative integers, determine whether it is a score sequence of a k-tournament or not. In this paper, we consider the score sequence problem of a tournament and of a k-tournament, and give efficient algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|