Random generation of tournaments and asymmetric graphs with given out-degrees

Random generation of tournaments and asymmetric graphs with given out-degrees

0.00 Avg rating0 Votes
Article ID: iaor19991393
Country: Netherlands
Volume: 95
Issue: 2
Start Page Number: 411
End Page Number: 419
Publication Date: Dec 1996
Journal: European Journal of Operational Research
Authors: , ,
Abstract:

In this paper, we first present a polynomial algorithm which computes a random tournament with given out-degrees; any tournament having these out-degrees has a nonzero probability to be computed. Then we give a necessary and sufficient condition for a sequence of numbers to be the out-degrees (or similarly the in-degrees) of an asymmetric graph. Lastly, using the above algorithm and this characterization, we design a second polynomial algorithm to compute a random asymmetric graph with given out-degrees, and any asymmetric graph with these out-degrees has a nonzero probability to be found.

Reviews

Required fields are marked *. Your email address will not be published.