Computer Science – Discrete Mathematics
Scientific paper
2010-03-21
Acta Univ. Sapientiae, Informatica, 1, 1 (2009) 71-88
Computer Science
Discrete Mathematics
Scientific paper
Let $a, b$ and $n$ be nonnegative integers $(b \geq a, \ b > 0, \ n \geq 1)$, $\mathcal{G}_n(a,b)$ be a multigraph on $n$ vertices in which any pair of vertices is connected with at least $a$ and at most $b$ edges and \textbf{v =} $(v_1, v_2, ..., v_n)$ be a vector containing $n$ nonnegative integers. We give a necessary and sufficient condition for the existence of such orientation of the edges of $\mathcal{G}_n(a,b)$, that the resulted out-degree vector equals to \textbf{v}. We describe a reconstruction algorithm. In worst case checking of \textbf{v} requires $\Theta(n)$ time and the reconstruction algorithm works in $O(bn^3)$ time. Theorems of H. G. Landau (1953) and J. W. Moon (1963) on the score sequences of tournaments are special cases $b = a = 1$ resp. $b = a \geq 1$ of our result.
No associations
LandOfFree
Reconstruction of complete interval tournaments 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction of complete interval tournaments will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-316751