Reconstruction of complete interval tournaments. II

Abstract

Let $a,b(b\ge a)$ and $n(n\ge 2)$ be nonnegative integers and let $\mathcal{T}(a,b,n)$ be the set of such generalised tournaments, in which every pair of distinct players is connected at most with $b$, and at least with $a$ arcs. In \cite{Ivanyi2009} we gave a necessary and sufficient condition to decide whether a given sequence of nonnegative integers $D=(d_1,d_2,...,d_n)$ can be realized as the out-degree sequence of a $T\in \mathcal{T}(a,b,n)$. Extending the results of \cite{Ivanyi2009} we show that for any sequence of nonnegative integers $D$ there exist $f$ and $g$ such that some element $T\in \mathcal{T}(g,f,n)$ has $D$ as its out-degree sequence, and for any $(a,b,n)$-tournament $T^{\prime }$ with the same out-degree sequence $D$ hold $a\le g$ and $b\ge f$. We propose a $\Theta (n)$ algorithm to determine $f$ and $g$ and an $O(d_n{n}^2)$ algorithm to construct a corresponding tournament $T$.

Cited by in corpus (1)

• Imbalances in directed multigraphs