Mathematics – Combinatorics
Scientific paper
2010-12-19
Acta Univ. Sapientiae, Mathematica, 2 (2010), 47--71
Mathematics
Combinatorics
Scientific paper
Let $a, \ b \ (b \geq a)$ and $n \ (n \geq 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'$ with the same out-degree sequence $D$ hold $a\leq g$ and $b\geq 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$.
No associations
LandOfFree
Reconstruction of complete interval tournaments. II does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Reconstruction of complete interval tournaments. II, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction of complete interval tournaments. II will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-452794