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: | Charon Irne, Hudry Olivier, Germa Anne |
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.