BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let n be a positive integer and X=[xij]1≤i,j≤n be an n×n\linebreak \noindent sized matrix of independent random variables having joint uniform distribution $$\hbox{Pr} {x_{ij} = k \hbox{for} 1 \leq k \leq n} = \frac{1}{n} \quad (1 \leq i, j \leq n) \koz. $$ A realization M=[mij] of X is called \textit{good}, if its each row and each column contains a permutation of the numbers 1,2,...,n. We present and analyse four typical algorithms which decide whether a given realization is good.
Let a,b and n be nonnegative integers (b≥a, b>0, n≥1), Gn(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 =} (v1,v2,...,vn) be a vector containing n nonnegative integers. We give a necessary and sufficient condition for the existence of such orientation of the edges of Gn(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 Θ(n) time and the reconstruction algorithm works in O(bn3) 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≥1 of our result.
Let a, b (b≥a) and n (n≥2) be nonnegative integers and let 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=(d1,d2,...,dn) can be realized as the out-degree sequence of a T∈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∈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≤g and b≥f. We propose a Θ(n) algorithm to determine f and g and an O(dnn2) algorithm to construct a corresponding tournament T.
Given non-negative integers ni and αi with 0≤αi≤ni (i=1,2,...,k), an [α1,α2,...,αk]-k-partite hypertournament on ∑1kni vertices is a (k+1)-tuple (U1,U2,...,Uk,E), where Ui are k vertex sets with ∣Ui∣=ni, and E is a set of ∑1kαi-tuples of vertices, called arcs, with exactly αi vertices from Ui, such that any ∑1kαi subset ∪1kUi′ of ∪1kUi, E contains exactly one of the (∑1kαi)! ∑1kαi-tuples whose entries belong to ∪1kUi′. We obtain necessary and sufficient conditions for k lists of non-negative integers in non-decreasing order to be the losing score lists and to be the score lists of some k-partite hypertournament.
Let ξ be a random integer vector, having uniform distribution P{ξ=(i1,i2,...,in)=1/nn} for 1≤i1,i2,...,in≤n. A realization (i1,i2,...,in) of ξ is called \textit{good}, if its elements are different. We present algorithms \textsc{Linear}, \textsc{Backward}, \textsc{Forward}, \textsc{Tree}, \textsc{Garbage}, \textsc{Bucket} which decide whether a given realization is good. We analyse the number of comparisons and running time of these algorithms using simulation gathering data on all possible inputs for small values of n and generating random inputs for large values of n.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.